-
Notifications
You must be signed in to change notification settings - Fork 0
/
dinic.cc
80 lines (74 loc) · 2.1 KB
/
dinic.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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
struct Dinic {
int n;
struct edge {int from, to; long long capacity, flow;};
vector<edge> edges, backward_edges;
vector<vector<int>> adj_forward, adj_backward;
vector<int> level;
Dinic(int n_ = 0) : n(n_), adj_forward(n_), adj_backward(n_), level(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(|V|^2 |E|) */
long long flow = 0, f;
while(bfs(s,t)) while ((f=dfs(s,t))) flow += f;
return flow;
}
private:
bool bfs(int s, int t) {
/* O(|E|) */
level.assign(n, -1);
level[s] = 0;
queue<int> q;
q.push(s);
while(q.size()) {
int v = q.front(); q.pop();
for(int i : adj_forward[v]) {
edge& e = edges[i];
if(level[e.to] != -1) continue;
if(e.capacity - e.flow == 0) continue;
level[e.to] = level[v] + 1;
q.push(e.to);
}
for(int i : adj_backward[v]) {
edge& e = backward_edges[i];
if(level[e.to] != -1) continue;
if(e.capacity - e.flow == 0) continue;
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
return level[t] != -1;
}
long long dfs(int v, int t, long long flow=1e18) {
/* O(|E|) */
if(v==t) return flow;
for(int i : adj_forward[v]) {
edge& e = edges[i];
if(level[e.to] <= level[v]) continue;
if(e.capacity - e.flow == 0) continue;
long long f = dfs(e.to, 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(level[e.to] <= level[v]) continue;
if(e.capacity - e.flow == 0) continue;
long long f = dfs(e.to, t, min(flow, e.capacity - e.flow));
if (f == 0) continue;
e.flow += f;
edges[i].flow -= f;
return f;
}
return 0;
}
};