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
|
/* Maximum-Flow solver using Dinic's Blocking Flow Algorithm.
Time Complexity:
- O(V^2 E) for general graphs, but in practice ~O(E^1.5)
- O(V^(1/2) E) for bipartite matching
- O(min(V^(2/3), E^(1/2)) E) for unit capacity graphs
*/
template<int V, class T = ll> class max_flow {
static const T INF = numeric_limits<T>::max();
struct edge {
int t, rev;
T cap, f;
};
vector<edge> adj[V];
int dist[V];
int ptr[V];
bool bfs(int s, int t) {
memset(dist, -1, sizeof dist);
dist[s] = 0;
queue<int> q({ s });
while (!q.empty() && dist[t] == -1) {
int n = q.front();
q.pop();
for (auto& e : adj[n]) {
if (dist[e.t] == -1 && e.cap != e.f) {
dist[e.t] = dist[n] + 1;
q.push(e.t);
}
}
}
return dist[t] != -1;
}
T augment(int n, T amt, int t) {
if (n == t) return amt;
for (; ptr[n] < adj[n].size(); ptr[n]++) {
edge& e = adj[n][ptr[n]];
if (dist[e.t] == dist[n] + 1 && e.cap != e.f) {
T flow = augment(e.t, min(amt, e.cap - e.f), t);
if (flow != 0) {
e.f += flow;
adj[e.t][e.rev].f -= flow;
return flow;
}
}
}
return 0;
}
public:
void add(int u, int v, T cap = 1, T rcap=0) {
adj[u].push_back({ v, (int) adj[v].size(), cap, 0 });
adj[v].push_back({ u, (int) adj[u].size() - 1, rcap, 0 });
}
T calc(int s, int t) {
T flow = 0;
while (bfs(s, t)) {
memset(ptr, 0, sizeof ptr);
while (T df = augment(s, INF, t)) flow += df;
}
return flow;
}
void clear() {
for (int n = 0; n < V; n++) adj[n].clear();
}
};
int main() {
max_flow<4> network;
network.add(0, 1, 75);
network.add(0, 2, 50);
network.add(1, 2, 40);
network.add(1, 3, 50);
network.add(2, 3, 30);
int flow = network.calc(0, 3);
cout << flow << endl; // Should be 80
}
|
