forked from nanwan03/poj
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1273 Drainage Ditches.java
57 lines (56 loc) · 1.42 KB
/
1273 Drainage Ditches.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int pathNumber = in.nextInt();
int nodeNumber = in.nextInt();
int[][] map = new int[nodeNumber + 1][nodeNumber + 1];
for (int i = 0; i < pathNumber; ++i) {
int from = in.nextInt();
int to = in.nextInt();
int cap = in.nextInt();
map[from][to] += cap;
}
int start = 1;
int end = nodeNumber;
System.out.println(edmondsKarp(map, start, end));
}
}
private static int edmondsKarp(int[][] map, int start, int end) {
int rst = 0;
int[] prev = new int[map.length];
while (bfs(map, prev, start, end)) {
int min = 0x3f3f3f3f;
for (int i = end; i != start; i = prev[i]) {
min = Math.min(min, map[prev[i]][i]);
}
for (int i = end; i != start; i = prev[i]) {
map[prev[i]][i] -= min;
map[i][prev[i]] += min;
}
rst += min;
}
return rst;
}
private static boolean bfs(int[][] map, int[] prev, int start, int nodeNumber) {
Arrays.fill(prev, -1);
prev[start] = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(start);
while (!queue.isEmpty()) {
int first = queue.poll();
for (int i = 1; i <= nodeNumber; ++i) {
if (prev[i] == -1 && map[first][i] != 0) {
queue.offer(i);
prev[i] = first;
if (i == nodeNumber) {
return true;
}
}
}
}
return false;
}
}