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
|
struct edge {
int from, to;
ll f, c;
};
vector<edge> edges;
vector<vector<int>> adjlist;
int s, t, dfsCounter;
vector<int> visited;
ll capacity;
void addEdge(int from, int to, ll c) {
adjlist[from].push_back(sz(edges));
edges.push_back({from, to, 0, c});
adjlist[to].push_back(sz(edges));
edges.push_back({to, from, 0, 0});
}
bool dfs(int x) {
if (x == t) return true;
if (visited[x] == dfsCounter) return false;
visited[x] = dfsCounter;
for (int id : adjlist[x]) {
if (edges[id].c >= capacity && dfs(edges[id].to)) {
edges[id].c -= capacity; edges[id ^ 1].c += capacity;
edges[id].f += capacity; edges[id ^ 1].f -= capacity;
return true;
}}
return false;
}
ll maxFlow(int source, int target) {
capacity = 1ll << 62;
s = source;
t = target;
ll flow = 0;
visited.assign(sz(adjlist), 0);
dfsCounter = 0;
while (capacity) {
while (dfsCounter++, dfs(s)) flow += capacity;
capacity /= 2;
}
return flow;
}
|
