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
|
struct Edge {
int to, rev;
ll f, c;
};
vector<vector<Edge>> adj;
int s, t;
vector<int> pt, dist;
void addEdge(int u, int v, ll c) {
adj[u].push_back({v, (int)sz(adj[v]), 0, c});
adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0});
}
bool bfs(ll lim) {
dist.assign(sz(adj), -1);
dist[s] = 0;
queue<int> q({s});
while (!q.empty() && dist[t] < 0) {
int v = q.front(); q.pop();
for (Edge& e : adj[v]) {
if (dist[e.to] < 0 && e.c - e.f >= lim) {
dist[e.to] = dist[v] + 1;
q.push(e.to);
}}}
return dist[t] >= 0;
}
ll dfs(int v, ll flow) {
if (v == t || flow == 0) return flow;
for (; pt[v] < sz(adj[v]); pt[v]++) {
Edge& e = adj[v][pt[v]];
if (dist[e.to] != dist[v] + 1) continue;
ll cur = dfs(e.to, min(e.c - e.f, flow));
if (cur > 0) {
e.f += cur;
adj[e.to][e.rev].f -= cur;
return cur;
}}
return 0;
}
ll maxFlow(int source, int target) {
s = source, t = target;
ll flow = 0;
for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
while (bfs(lim)) {
pt.assign(sz(adj), 0);
ll cur;
do {
cur = dfs(s, lim);
flow += cur;
} while (cur > 0);
}}
return flow;
}
|
