-
Notifications
You must be signed in to change notification settings - Fork 1
/
MaxFlowPreflowN3.java
89 lines (77 loc) · 1.79 KB
/
MaxFlowPreflowN3.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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package Flows;
public class MaxFlowPreflowN3 {
int[][] cap;
public void init(int nodes) {
cap = new int[nodes][nodes];
}
public void addEdge(int s, int t, int capacity) {
cap[s][t] = capacity;
}
public int maxFlow(int s, int t) {
int n = cap.length;
int[] h = new int[n];
h[s] = n - 1;
int[] maxh = new int[n];
int[][] f = new int[n][n];
int[] e = new int[n];
for (int i = 0; i < n; ++i) {
f[s][i] = cap[s][i];
f[i][s] = -f[s][i];
e[i] = cap[s][i];
}
for (int sz = 0;;) {
if (sz == 0) {
for (int i = 0; i < n; ++i)
if (i != s && i != t && e[i] > 0) {
if (sz != 0 && h[i] > h[maxh[0]])
sz = 0;
maxh[sz++] = i;
}
}
if (sz == 0)
break;
while (sz != 0) {
int i = maxh[sz - 1];
boolean pushed = false;
for (int j = 0; j < n && e[i] != 0; ++j) {
if (h[i] == h[j] + 1 && cap[i][j] - f[i][j] > 0) {
int df = Math.min(cap[i][j] - f[i][j], e[i]);
f[i][j] += df;
f[j][i] -= df;
e[i] -= df;
e[j] += df;
if (e[i] == 0)
--sz;
pushed = true;
}
}
if (!pushed) {
h[i] = Integer.MAX_VALUE;
for (int j = 0; j < n; ++j)
if (h[i] > h[j] + 1 && cap[i][j] - f[i][j] > 0)
h[i] = h[j] + 1;
if (h[i] > h[maxh[0]]) {
sz = 0;
break;
}
}
}
}
int flow = 0;
for (int i = 0; i < n; i++)
flow += f[s][i];
return flow;
}
// Usage example
public static void main(String[] args) {
int[][] capacity = { { 0, 3, 2 }, { 0, 0, 2 }, { 0, 0, 0 } };
int n = capacity.length;
MaxFlowPreflowN3 flow = new MaxFlowPreflowN3();
flow.init(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (capacity[i][j] != 0)
flow.addEdge(i, j, capacity[i][j]);
System.out.println(4 == flow.maxFlow(0, 2));
}
}