-
Notifications
You must be signed in to change notification settings - Fork 0
/
ford_fulkerson.cc
60 lines (56 loc) · 1.67 KB
/
ford_fulkerson.cc
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
struct FordFulkerson {
const static long long INF=numeric_limits<long long>::max()/2;
int n;
struct edge {int from, to; long long capacity, flow;};
vector<edge> edges, backward_edges;
vector<vector<int>> adj_forward, adj_backward;
FordFulkerson(int n_ = 0) : n(n_), adj_forward(n_), adj_backward(n_) { }
int add_edge(int from, int to, long long capacity) {
/* O(1) */
int index = ssize(edges);
adj_forward[from].push_back(index);
adj_backward[to].push_back(index);
edges.push_back({from, to, capacity, 0});
backward_edges.push_back({to, from, 0, 0});
return index;
}
long long maxflow(int s, int t) {
/* O(|E|f) f=maxflow */
long long flow = 0;
vector<bool> visited(n);
while(true) {
visited.assign(n, false);
long long f = dfs(s, visited, t);
if(f==0) return flow;
flow += f;
}
return 0; // dummy
}
private:
long long dfs(int v, vector<bool> &visited, int t, long long flow=INF) {
/* O(|E|) */
if(v==t) return flow;
visited[v] = true;
for(int i : adj_forward[v]) {
edge& e = edges[i];
if(visited[e.to]) continue;
if(e.capacity - e.flow == 0) continue;
long long f = dfs(e.to, visited, t, min(flow, e.capacity - e.flow));
if (f == 0) continue;
e.flow += f;
backward_edges[i].flow -= f;
return f;
}
for(int i : adj_backward[v]) {
edge& e = backward_edges[i];
if(visited[e.to]) continue;
if(e.capacity - e.flow == 0) continue;
long long f = dfs(e.to, visited, t, min(flow, e.capacity - e.flow));
if (f == 0) continue;
e.flow += f;
edges[i].flow -= f;
return f;
}
return 0;
}
};