-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaxFlow3.java
77 lines (66 loc) · 1.41 KB
/
MaxFlow3.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
package graphs.max_flow;
import java.util.LinkedList;
import java.util.Queue;
//Try to test the implementation with some input of your choice
public class MaxFlow3 {
static final int INF = (int)1e9;
static int V, s, t, c[][]; //input
static int pushRelabel() //O(V^3)
{
int[] h = new int[V], e = new int[V], f[] = new int[V][V];
h[s] = V - 1;
Queue<Integer> q = new LinkedList<Integer>();
q.add(t);
while(!q.isEmpty())
{
int u = q.remove();
for(int v = 0; v < V; ++v)
if(v != t && v != s && h[v] == 0)
{
h[v] = h[u] + 1;
q.add(v);
}
}
boolean[] isActive = new boolean[V];
for(int i = 0; i < V; ++i)
{
f[i][s] = -(f[s][i] = e[i] = c[s][i]);
if(i != s && i != t && e[i] > 0)
{
isActive[i] = true;
q.add(i);
}
}
while(!q.isEmpty())
{
int u = q.peek();
boolean pushed = false;
for(int v = 0; v < V && e[u] != 0; ++v)
if(h[u] == h[v] + 1 && c[u][v] - f[u][v] > 0)
{
int df = Math.min(e[u], c[u][v] - f[u][v]);
f[u][v] += df; f[v][u] -= df;
e[u] -= df; e[v] += df;
if(v != s && v != t && !isActive[v])
{
isActive[v] = true;
q.add(v);
}
pushed = true;
}
if(e[u] == 0)
{
isActive[u] = false;
q.remove();
}
if(!pushed)
{
h[u] = INF;
for(int v = 0; v < V; ++v)
if(h[v] + 1 < h[u] && c[u][v] - f[u][v] > 0)
h[u] = h[v] + 1;
}
}
return e[t];
}
}