These are the notes for Competitive Programming episode 58. A flow network is a directed graph whose edges have capacities; a flow sends an amount along each edge, never more than its capacity, with in = out at every vertex except the source and the sink. The maximum flow is the largest total that reaches the sink. Water for the Town shows that filling any path greedily is wrong (19 instead of 23), because a bad first choice can't be undone; adding a reverse edge for every edge (the residual graph) fixes it (Ford-Fulkerson), but depth-first paths are Time Limit Exceeded on 5000 junctions and 10^5 pipes. Dinic's algorithm pushes only along BFS levels and finds a blocking flow with a current-edge pointer it[v]: accepted in a fraction of a second, once the total is a long long (an int prints -2081215223). Stop the Smugglers uses the max-flow min-cut theorem: the cheapest set of roads to close costs exactly the max flow, and the roads are read off after the last BFS; a two-way road added as one-way prints cost 3 where cost 6 is right. A stress test against every possible cut passes. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
The water board connects a tank to a town with one-way pipes, each with a limit in litres per second. Junctions store nothing: what flows in flows out. How much water can reach the town every second? Planners first try "pick a route, fill it, repeat", then notice that one early decision (sending water on a detour) blocks better routes later. The fix is to realise that sending water back along a pipe simply cancels some of what we sent: every decision has an undo.
Definitions
- Capacity c(a → b): the most the pipe can carry.
- Flow f(a → b): what it carries, 0 ≤ f ≤ c. Conservation: at every junction except the source s and sink t, total in = total out.
- Value of a flow: the total leaving s (= the total entering t).
- Residual capacity: c − f forwards (room left), and f backwards (how much can be cancelled).
- Augmenting path: an s → t path in the residual graph with positive residual capacity on every edge.
- Cut (S, T): a split of the vertices with s ∈ S and t ∈ T; its capacity is the sum of c(a → b) over edges with a ∈ S, b ∈ T.
Problem F1 · Water for the Town
(Written for this course, in the style of a classic flow problem.)
- Input: n m (n ≤ 5000, m ≤ 10^5), then m lines a b c (pipe a → b, capacity c ≤ 10^9).
- Output: the maximum flow from junction 1 to junction n.
6 10
1 2 16
1 3 13
2 4 12
2 3 10
3 2 4
3 5 14
4 3 9
4 6 20
5 4 7
5 6 4
| Pipe | 1→2 | 1→3 | 2→4 | 2→3 | 3→2 | 3→5 | 4→3 | 4→6 | 5→4 | 5→6 |
|---|---|---|---|---|---|---|---|---|---|---|
| Capacity | 16 | 13 | 12 | 10 | 4 | 14 | 9 | 20 | 7 | 4 |
The tank is 1 and the town is 6. The answer is 23: the cut {1, 2, 3, 5} | {4, 6} has capacity 12 + 7 + 4 = 23.
The obvious attempt: fill any path (WA)
Each pipe is an Edge {to, cap}; push is a DFS that returns how much it sent along one path and subtracts it from every pipe on the way.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
}
bool vis[5001];
ll push(int v, ll f) { // DFS: any path with spare capacity
if (v == n) return f;
vis[v] = true;
for (int id : g[v]) {
auto [u, cap] = e[id];
if (cap > 0 && !vis[u])
if (ll d = push(u, min(f, cap))) {
e[id].cap -= d;
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addPipe(a, b, c);
}
ll flow = 0;
while (true) {
memset(vis, 0, sizeof vis);
ll d = push(1, LLONG_MAX);
if (!d) break;
flow += d;
}
cout << flow << "\n";
}
19
The DFS first finds 1 → 2 → 4 → 3 → 5 → 6 (4 L/s, limited by 5 → 6), a detour that uses the whole pipe 5 → 6 and part of 2 → 4. Then 1 → 2 → 4 → 6 (8), 1 → 2 → 3 → 5 → 4 → 6 (4) and 1 → 3 → 5 → 4 → 6 (3): 19 in total, and no path with room is left. The maximum is 23.
Reverse edges: the residual graph (Ford-Fulkerson)
For every pipe a → b add a reverse pipe b → a with capacity 0, stored right after it, so the twin of edge id is id ^ 1. When a path pushes d along id, do cap[id] -= d and cap[id ^ 1] += d. A later path through the reverse pipe cancels flow: the water on the detour 4 → 3 can be re-routed.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
bool vis[5001];
ll push(int v, ll f) { // DFS: any path with spare capacity
if (v == n) return f;
vis[v] = true;
for (int id : g[v]) {
auto [u, cap] = e[id];
if (cap > 0 && !vis[u])
if (ll d = push(u, min(f, cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d; // it can be sent back later
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addPipe(a, b, c);
}
ll flow = 0;
while (true) {
memset(vis, 0, sizeof vis);
ll d = push(1, LLONG_MAX);
if (!d) break;
flow += d;
}
cout << flow << "\n";
}
23
Why it is correct: when no augmenting path is left, let S be the vertices reachable from s in the residual graph. Every edge from S to T is full and every edge from T to S carries nothing (otherwise its reverse would have room), so the flow equals the capacity of the cut (S, T). Since every flow is at most every cut, it is maximum.
Why it is slow: each round is a full DFS, and the number of rounds depends on the paths found; with DFS it can grow with the flow value F itself, O(E · F). A random city of 5000 junctions and 10^5 pipes with capacities up to 10^9:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
bool vis[5001];
ll push(int v, ll f) { // DFS: any path with spare capacity
if (v == n) return f;
vis[v] = true;
for (int id : g[v]) {
auto [u, cap] = e[id];
if (cap > 0 && !vis[u])
if (ll d = push(u, min(f, cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d; // it can be sent back later
return d;
}
}
return 0;
}
int main() {
n = 5000, m = 100000; // a random city
mt19937 rng(58);
for (int i = 0; i < m; i++) {
int a = rng() % n + 1, b = rng() % n + 1;
if (a != b) addPipe(a, b, rng() % 1000000000 + 1);
}
ll flow = 0;
while (true) {
memset(vis, 0, sizeof vis);
ll d = push(1, LLONG_MAX);
if (!d) break;
flow += d;
}
cout << flow << "\n";
}
Time Limit Exceeded
Dinic's algorithm
- BFS from the source over edges with room:
lvl[v]= the fewest edges from s to v. - Push only along edges with
lvl[u] == lvl[v] + 1: every path is a shortest path in the residual graph. - Keep pushing until t can't be reached in this level graph: a blocking flow. Each vertex keeps
it[v], the first edge not yet known to be useless;for (int &i = it[v]; …)advances it, so a dead edge is never tried twice in a phase. - Repeat from 1. The distance from s to t strictly increases every phase, so there are at most V phases. Each phase is O(V · E), giving the classic bound O(V² E); on unit-capacity graphs it is O(E √V).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addPipe(a, b, c);
}
ll flow = 0;
while (bfs(1, n)) { // one phase per level graph
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) flow += d;
}
cout << flow << "\n";
}
23
A single pipe:
5
The bug: an int total
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
n = 5000, m = 100000; // a random city
mt19937 rng(58);
for (int i = 0; i < m; i++) {
int a = rng() % n + 1, b = rng() % n + 1;
if (a != b) addPipe(a, b, rng() % 1000000000 + 1);
}
int flow = 0;
while (bfs(1, n)) { // one phase per level graph
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) flow += d;
}
cout << flow << "\n";
}
-2081215223
The true answer, 6,508,719,369, is more than INT_MAX = 2,147,483,647. With long long:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
n = 5000, m = 100000; // a random city
mt19937 rng(58);
for (int i = 0; i < m; i++) {
int a = rng() % n + 1, b = rng() % n + 1;
if (a != b) addPipe(a, b, rng() % 1000000000 + 1);
}
ll flow = 0;
while (bfs(1, n)) { // one phase per level graph
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) flow += d;
}
cout << flow << "\n";
}
6508719369
Problem F2 · Stop the Smugglers
(Written for this course.)
n towns and m two-way roads; closing road i costs c[i]. Find the cheapest set of roads whose closing disconnects the port (1) from the capital (n), and print the roads.
- Input: n m, then m lines a b c.
- Output:
cost X, thenclose:and the road numbers.
6 8
2 1 5
1 3 4
3 2 3
4 2 2
3 5 6
5 4 1
6 4 7
5 6 3
The max-flow min-cut theorem
- Every flow ≤ every cut: everything reaching t crosses the cut.
- When Dinic stops, the vertices with
lvl[v] ≥ 0(reached by the last, failed BFS) form a set S whose outgoing edges are all full: flow = cut(S, T). - So max flow = min cut, and the cut edges are the roads with one end in S and the other in T.
A two-way road with closing cost c is a pipe of capacity c in both directions: the forward edge and its twin both start at c (the twin is then both the reverse road and the undo).
The bug: a two-way road added as one-way
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addRoad(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0});
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addRoad(a, b, c);
}
ll cost = 0;
while (bfs(1, n)) {
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) cost += d;
}
cout << "cost " << cost << "\nclose:";
for (int i = 0; i < m; i++) { // lvl >= 0: still reachable from the port
int a = e[2 * i + 1].to, b = e[2 * i].to;
if ((lvl[a] >= 0) != (lvl[b] >= 0)) cout << " " << i + 1;
}
cout << "\n";
}
cost 3
close: 7 8
Road 1 is written 2 1, so the code allows only 2 → 1, and the smugglers' routes through road 1 vanish. With capacity c both ways:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addRoad(int a, int b, ll c) { // a two-way road
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, c}); // the other direction is a real road too
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addRoad(a, b, c);
}
ll cost = 0;
while (bfs(1, n)) {
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) cost += d;
}
cout << "cost " << cost << "\nclose:";
for (int i = 0; i < m; i++) { // lvl >= 0: still reachable from the port
int a = e[2 * i + 1].to, b = e[2 * i].to;
if ((lvl[a] >= 0) != (lvl[b] >= 0)) cout << " " << i + 1;
}
cout << "\n";
}
cost 6
close: 4 6 8
Roads 4 (2–4, cost 2), 6 (5–4, cost 1) and 8 (5–6, cost 3) cost 6.
Stress test: max flow = the cheapest cut
For n ≤ 8, try every set S containing 1 and not n, add the capacities of the edges leaving S, and compare the minimum with Dinic.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
mt19937 rng(58);
for (int t = 1; t <= 500; t++) {
n = rng() % 7 + 2, m = rng() % 12;
e.clear();
for (int v = 1; v <= n; v++) g[v].clear();
vector<array<int, 3>> pipes;
for (int i = 0; i < m; i++) {
int a = rng() % n + 1, b = rng() % n + 1, c = rng() % 10;
pipes.push_back({a, b, c});
addPipe(a, b, c);
}
ll best = LLONG_MAX; // brute force: try every cut
for (int mask = 0; mask < (1 << n); mask++) {
if (!(mask & 1) || (mask >> (n - 1) & 1)) continue; // tank in, town out
ll cut = 0;
for (auto [a, b, c] : pipes)
if ((mask >> (a - 1) & 1) && !(mask >> (b - 1) & 1)) cut += c;
best = min(best, cut);
}
ll flow = 0;
while (bfs(1, n)) {
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) flow += d;
}
if (flow != best) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Verdict at n = 5000, m = 10^5 |
|---|---|---|
| fill any path, no reverse edges | fast | Wrong Answer |
| Ford-Fulkerson with DFS | O(E · F) | TLE |
| Edmonds-Karp (BFS paths, one at a time) | O(V E²) | often too slow |
| Dinic | O(V² E) bound, much faster in practice | accepted (≈ 0.02 s here) |
| Dinic on unit capacities (matching) | O(E √V) | accepted |
| min cut after the flow | + O(V + E) | accepted |
Memory: two edges per pipe (or per road), 2 · 10^5 edges.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| no reverse edges | 19 (expected 23) |
choices can't be undone | e[id ^ 1].cap += d |
| DFS paths on big graphs | Time Limit Exceeded |
O(E · F) rounds | Dinic |
int flow with c ≤ 10^9 |
-2081215223 |
overflow | long long |
| a two-way road as one pipe | cost 3 (expected cost 6) |
one direction missing | capacity c both ways |
it[v] not reset each phase |
too small a flow | edges skipped forever | fill(it, it + n + 1, 0) |
no it[v] at all |
very slow phases | dead edges retried | for (int &i = it[v]; …) |
reverse edge not at id ^ 1 |
wrong twins, garbage | push both edges together | addPipe pushes both |
| cut read from the residual before the flow ends | wrong roads | S must come from the last BFS | use lvl after bfs fails |
Mini project
Build a reusable Dinic struct: addEdge(a, b, cap, revCap = 0), maxflow(s, t), minCut() (vertices on the source side) and flowOn(edgeId). Test it on: the sample, a single edge, s = t (should be rejected), two parallel edges, an edge into s or out of t, and the stress test above. Then solve homework 1–4 with it.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Several tanks and several towns. Pipes as in F1, then the list of tanks and the list of towns.
Solution
Add a super source 0 with an edge of "infinite" capacity to every tank, and a super sink n + 1 with one from every town. Sample: tanks 1, 2 feed junction 3 (4 + 5), which feeds towns 4 (6) and 5 (2): 8.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; };
vector<Edge> e;
vector<int> g[5005];
int n, m, lvl[5005], it[5005];
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0});
}
bool bfs(int s, int t, int V) {
fill(lvl, lvl + V, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) {
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
ll maxflow(int s, int t, int V) {
ll flow = 0;
while (bfs(s, t, V)) {
fill(it, it + V, 0);
while (ll d = dfs(s, t, LLONG_MAX)) flow += d;
}
return flow;
}
int main() {
// n junctions, m pipes, then the tanks and the towns. Super source 0, super sink n + 1.
int a_cnt, b_cnt;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addPipe(a, b, c);
}
cin >> a_cnt;
for (int i = 0; i < a_cnt; i++) { int x; cin >> x; addPipe(0, x, LLONG_MAX / 4); }
cin >> b_cnt;
for (int i = 0; i < b_cnt; i++) { int x; cin >> x; addPipe(x, n + 1, LLONG_MAX / 4); }
cout << maxflow(0, n + 1, n + 2) << "\n";
}
8
2. Junctions with their own limit. Junction v can pass at most lim[v] per second.
Solution
Split v into v_in and v_out with one edge v_in → v_out of capacity lim[v]. Every pipe a → b becomes a_out → b_in. Sample: two routes through junctions 2 and 3, limited to 3 and 4: 7.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; };
vector<Edge> e;
vector<int> g[5005];
int n, m, lvl[5005], it[5005];
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0});
}
bool bfs(int s, int t, int V) {
fill(lvl, lvl + V, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) {
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
ll maxflow(int s, int t, int V) {
ll flow = 0;
while (bfs(s, t, V)) {
fill(it, it + V, 0);
while (ll d = dfs(s, t, LLONG_MAX)) flow += d;
}
return flow;
}
int main() {
// junction v has a limit lim[v]: v_in = v, v_out = v + N, one pipe v_in -> v_out of capacity lim[v]
cin >> n >> m;
const int N = 2000;
for (int v = 1; v <= n; v++) {
ll lim;
cin >> lim;
addPipe(v, v + N, lim);
}
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addPipe(a + N, b, c); // leave a through a_out, enter b through b_in
}
cout << maxflow(1, n + N, 2 * N + 1) << "\n";
}
7
3. The fewest roads to close (every road costs 1).
Solution
A min cut with all capacities 1 counts roads. Two-way roads: capacity 1 in both directions. (By Menger's theorem this also equals the most routes from 1 to n sharing no road.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; };
vector<Edge> e;
vector<int> g[5005];
int n, m, lvl[5005], it[5005];
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0});
}
bool bfs(int s, int t, int V) {
fill(lvl, lvl + V, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) {
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
ll maxflow(int s, int t, int V) {
ll flow = 0;
while (bfs(s, t, V)) {
fill(it, it + V, 0);
while (ll d = dfs(s, t, LLONG_MAX)) flow += d;
}
return flow;
}
int main() {
// two-way roads, every road costs 1 to close: the min cut counts roads
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(e.size());
e.push_back({b, 1});
g[b].push_back(e.size());
e.push_back({a, 1});
}
cout << maxflow(1, n, n + 1) << "\n";
}
2
4. The most paths from 1 to n sharing no pipe (and print them).
Solution
Capacity 1 on every pipe; the max flow k is the number of edge-disjoint paths. To print them, walk from 1 along forward edges that carry flow (cap == 0 on a forward edge with capacity 1), marking each used edge.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; };
vector<Edge> e;
vector<int> g[5005];
int n, m, lvl[5005], it[5005];
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0});
}
bool bfs(int s, int t, int V) {
fill(lvl, lvl + V, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) {
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
ll maxflow(int s, int t, int V) {
ll flow = 0;
while (bfs(s, t, V)) {
fill(it, it + V, 0);
while (ll d = dfs(s, t, LLONG_MAX)) flow += d;
}
return flow;
}
int main() {
// one-way pipes, capacity 1 each: max flow = the most paths sharing no pipe; print them
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
addPipe(a, b, 1);
}
ll k = maxflow(1, n, n + 1);
cout << k << " paths\n";
for (int p = 0; p < k; p++) { // follow used pipes (forward pipe with cap 0) from 1 to n
int v = 1;
cout << 1;
while (v != n)
for (int id : g[v])
if (id % 2 == 0 && e[id].cap == 0) {
e[id].cap = -1; // use each pipe once
v = e[id].to;
cout << " " << v;
break;
}
cout << "\n";
}
}
2 paths
1 2 4 6
1 3 6
Quick quiz
Five pipes. What is the max flow from 1 to 4?
1→2: 3 1→3: 2 2→3: 5 2→4: 2 3→4: 4
A) 2 · B) 4 · C) 5 · D) 6
Answer
C. The cut {1} | {2, 3, 4} has capacity 3 + 2 = 5, so the flow is at most 5. The paths 1→2→4 (2), 1→2→3→4 (1) and 1→3→4 (2) send 5.
Interview questions
- What is the max-flow min-cut theorem? The maximum value of an s–t flow equals the minimum capacity of an s–t cut.
- Why do we need reverse edges? They let a later augmenting path cancel flow sent earlier; without them a greedy choice can't be undone and the result can be smaller than the maximum.
- Ford-Fulkerson vs Edmonds-Karp vs Dinic? FF: any augmenting path, O(E · F). EK: shortest augmenting paths by BFS, O(V E²). Dinic: all shortest paths of a phase at once (blocking flow), O(V² E), O(E √V) for unit capacities.
- What is a blocking flow? A flow in the level graph after which every s–t path in the level graph has a saturated edge.
- Why does Dinic have at most V phases? Each phase strictly increases the s–t distance in the residual graph, and that distance is at most V − 1.
- How do you find the min cut edges? After the flow, BFS from s in the residual graph; edges from reached to unreached vertices form a minimum cut.
- How do you handle undirected edges and vertex capacities? Undirected: capacity c both ways. Vertex capacity: split v into v_in → v_out.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Flow network | A directed graph with edge capacities, a source and a sink | the water board |
| Source / sink | Where flow starts / ends | tank 1 / town n |
| Capacity | The most an edge can carry | 1 → 2: 16 |
| Flow | The amount on each edge, 0 ≤ f ≤ c, with in = out at every inner vertex | 23 in total |
| Conservation | In = out at every vertex except s and t | junctions store nothing |
| Max flow | The largest flow value | 23 |
| Residual capacity | Room left forwards (c − f) and cancellable backwards (f) | reverse 3 → 4 |
| Residual graph | The graph of edges with positive residual capacity | Ford-Fulkerson |
| Reverse edge | The twin edge id ^ 1 that undoes flow |
e[id ^ 1].cap += d |
| Augmenting path | An s → t path with room on every edge | 1 → 2 → 4 → 6 |
| Bottleneck | The smallest residual capacity on a path | 4 on the first path |
| Ford-Fulkerson | Augment along any path until none is left | DFS paths |
| Edmonds-Karp | Ford-Fulkerson with BFS (shortest) paths | O(V E²) |
| Level graph | Edges from level L to L + 1 after a BFS | Dinic step 2 |
| Blocking flow | A flow that saturates some edge on every level-graph path | Dinic step 3 |
Current-edge pointer it[v] |
The first edge of v still worth trying in this phase | for (int &i = it[v]; …) |
| Dinic's algorithm | BFS levels + blocking flows, repeated | O(V² E) |
| Cut (S, T) | A split with s ∈ S, t ∈ T; capacity = edges S → T | {1, 2, 3, 5} |
| Min cut | The cut of smallest capacity | 12 + 7 + 4 = 23 |
| Max-flow min-cut theorem | max flow = min cut | F2 |
| Super source / super sink | Extra vertices joining many sources / sinks | homework 1 |
| Vertex splitting | v → v_in, v_out to give a vertex a capacity | homework 2 |
| Edge-disjoint paths | Paths that share no edge | homework 4 |
| Integer overflow | A result too big for its type | -2081215223 |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| Time Limit Exceeded (TLE) | Too slow | Ford-Fulkerson on the city |
| Wrong Answer (WA) | A wrong output | 19, cost 3 |
| Bipartite matching | Pairing two sides with no shared ends | next episode |
Summary
- A flow respects capacities and conservation; the max flow is the most that reaches the sink.
- Greedy paths get stuck (
19vs23); reverse edges (id ^ 1) make every choice undoable: the residual graph. - Ford-Fulkerson is correct but can be O(E · F): TLE on big graphs.
- Dinic: BFS levels, then a blocking flow with
it[v]; at most V phases; accepted easily. - Sum capacities in
long long(-2081215223otherwise). - Max flow = min cut; the cut is read from
lvlafter the last BFS; two-way roads get capacity c both ways.
Solutions in C++, Java and Python
Problem F1 · Water for the Town
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addPipe(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, 0}); // reverse pipe: e[id ^ 1], the undo
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addPipe(a, b, c);
}
ll flow = 0;
while (bfs(1, n)) { // one phase per level graph
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) flow += d;
}
cout << flow << "\n";
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int[] to, head, nxt, lvl, it;
static long[] cap;
static int cnt = 0, n;
static void addPipe(int a, int b, long c) { // edge i and its reverse i ^ 1
to[cnt] = b; cap[cnt] = c; nxt[cnt] = head[a]; head[a] = cnt++;
to[cnt] = a; cap[cnt] = 0; nxt[cnt] = head[b]; head[b] = cnt++;
}
static boolean bfs(int s, int t) {
Arrays.fill(lvl, -1);
lvl[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
for (int id = head[v]; id != -1; id = nxt[id])
if (cap[id] > 0 && lvl[to[id]] < 0) { lvl[to[id]] = lvl[v] + 1; q.add(to[id]); }
}
return lvl[t] >= 0;
}
static long dfs(int v, int t, long f) {
if (v == t) return f;
for (; it[v] != -1; it[v] = nxt[it[v]]) {
int id = it[v], u = to[id];
if (cap[id] > 0 && lvl[u] == lvl[v] + 1) {
long d = dfs(u, t, Math.min(f, cap[id]));
if (d > 0) { cap[id] -= d; cap[id ^ 1] += d; return d; }
}
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tk = new StringTokenizer(br.readLine());
n = Integer.parseInt(tk.nextToken());
int m = Integer.parseInt(tk.nextToken());
to = new int[2 * m]; nxt = new int[2 * m]; cap = new long[2 * m];
head = new int[n + 1]; lvl = new int[n + 1]; it = new int[n + 1];
Arrays.fill(head, -1);
for (int i = 0; i < m; i++) {
tk = new StringTokenizer(br.readLine());
addPipe(Integer.parseInt(tk.nextToken()), Integer.parseInt(tk.nextToken()), Long.parseLong(tk.nextToken()));
}
long flow = 0;
while (bfs(1, n)) {
System.arraycopy(head, 0, it, 0, n + 1);
long d;
while ((d = dfs(1, n, Long.MAX_VALUE)) > 0) flow += d;
}
System.out.println(flow);
}
}
23
Python (recursive DFS; fine for the sample, slow for 10^5 pipes)
import sys
from collections import deque
sys.setrecursionlimit(20000)
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
to, cap, g = [], [], [[] for _ in range(n + 1)]
def add_pipe(a, b, c): # edge i and its reverse i ^ 1
g[a].append(len(to)); to.append(b); cap.append(c)
g[b].append(len(to)); to.append(a); cap.append(0)
for i in range(m):
a, b, c = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
add_pipe(a, b, c)
def bfs():
lvl = [-1] * (n + 1); lvl[1] = 0
q = deque([1])
while q:
v = q.popleft()
for i in g[v]:
if cap[i] > 0 and lvl[to[i]] < 0:
lvl[to[i]] = lvl[v] + 1; q.append(to[i])
return lvl
def dfs(v, f, lvl, it):
if v == n:
return f
while it[v] < len(g[v]):
i = g[v][it[v]]; u = to[i]
if cap[i] > 0 and lvl[u] == lvl[v] + 1:
d = dfs(u, min(f, cap[i]), lvl, it)
if d:
cap[i] -= d; cap[i ^ 1] += d
return d
it[v] += 1
return 0
flow = 0
while True:
lvl = bfs()
if lvl[n] < 0:
break
it = [0] * (n + 1)
while True:
d = dfs(1, float("inf"), lvl, it)
if not d:
break
flow += d
print(flow)
main()
23
Problem F2 · Stop the Smugglers
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int to; ll cap; }; // cap = water it can still carry
vector<Edge> e;
vector<int> g[5001]; // g[v] = ids of pipes out of v
int n, m;
void addRoad(int a, int b, ll c) { // a two-way road
g[a].push_back(e.size());
e.push_back({b, c});
g[b].push_back(e.size());
e.push_back({a, c}); // the other direction is a real road too
}
int lvl[5001], it[5001];
bool bfs(int s, int t) { // level = pipes from the tank
fill(lvl, lvl + n + 1, -1);
lvl[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v])
if (e[id].cap > 0 && lvl[e[id].to] < 0) {
lvl[e[id].to] = lvl[v] + 1;
q.push(e[id].to);
}
}
return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) { // only to the next level
if (v == t) return f;
for (int &i = it[v]; i < (int)g[v].size(); i++) { // skip pipes already tried
int id = g[v][i], u = e[id].to;
if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
if (ll d = dfs(u, t, min(f, e[id].cap))) {
e[id].cap -= d;
e[id ^ 1].cap += d;
return d;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
addRoad(a, b, c);
}
ll cost = 0;
while (bfs(1, n)) {
fill(it, it + n + 1, 0);
while (ll d = dfs(1, n, LLONG_MAX)) cost += d;
}
cout << "cost " << cost << "\nclose:";
for (int i = 0; i < m; i++) { // lvl >= 0: still reachable from the port
int a = e[2 * i + 1].to, b = e[2 * i].to;
if ((lvl[a] >= 0) != (lvl[b] >= 0)) cout << " " << i + 1;
}
cout << "\n";
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int[] to, head, nxt, lvl, it;
static long[] cap;
static int cnt = 0, n;
static void addRoad(int a, int b, long c) { // road i = edges 2i, 2i + 1: c in both directions
to[cnt] = b; cap[cnt] = c; nxt[cnt] = head[a]; head[a] = cnt++;
to[cnt] = a; cap[cnt] = c; nxt[cnt] = head[b]; head[b] = cnt++;
}
static boolean bfs(int s, int t) {
Arrays.fill(lvl, -1);
lvl[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
for (int id = head[v]; id != -1; id = nxt[id])
if (cap[id] > 0 && lvl[to[id]] < 0) { lvl[to[id]] = lvl[v] + 1; q.add(to[id]); }
}
return lvl[t] >= 0;
}
static long dfs(int v, int t, long f) {
if (v == t) return f;
for (; it[v] != -1; it[v] = nxt[it[v]]) {
int id = it[v], u = to[id];
if (cap[id] > 0 && lvl[u] == lvl[v] + 1) {
long d = dfs(u, t, Math.min(f, cap[id]));
if (d > 0) { cap[id] -= d; cap[id ^ 1] += d; return d; }
}
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tk = new StringTokenizer(br.readLine());
n = Integer.parseInt(tk.nextToken());
int m = Integer.parseInt(tk.nextToken());
to = new int[2 * m]; nxt = new int[2 * m]; cap = new long[2 * m];
head = new int[n + 1]; lvl = new int[n + 1]; it = new int[n + 1];
Arrays.fill(head, -1);
for (int i = 0; i < m; i++) {
tk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(tk.nextToken()), b = Integer.parseInt(tk.nextToken());
long c = Long.parseLong(tk.nextToken());
addRoad(a, b, c);
}
long cost = 0;
while (bfs(1, n)) {
System.arraycopy(head, 0, it, 0, n + 1);
long d;
while ((d = dfs(1, n, Long.MAX_VALUE)) > 0) cost += d;
}
StringBuilder sb = new StringBuilder("cost " + cost + "\nclose:");
for (int i = 0; i < m; i++) // lvl >= 0: still reachable from the port
if ((lvl[to[2 * i + 1]] >= 0) != (lvl[to[2 * i]] >= 0)) sb.append(" ").append(i + 1);
System.out.println(sb);
}
}
cost 6
close: 4 6 8
Python
import sys
from collections import deque
sys.setrecursionlimit(20000)
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
to, cap, g = [], [], [[] for _ in range(n + 1)]
for i in range(m):
a, b, c = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
g[a].append(len(to)); to.append(b); cap.append(c) # road i = edges 2i and 2i + 1
g[b].append(len(to)); to.append(a); cap.append(c) # two-way: c in both directions
def bfs():
lvl = [-1] * (n + 1); lvl[1] = 0
q = deque([1])
while q:
v = q.popleft()
for i in g[v]:
if cap[i] > 0 and lvl[to[i]] < 0:
lvl[to[i]] = lvl[v] + 1; q.append(to[i])
return lvl
def dfs(v, f, lvl, it):
if v == n:
return f
while it[v] < len(g[v]):
i = g[v][it[v]]; u = to[i]
if cap[i] > 0 and lvl[u] == lvl[v] + 1:
d = dfs(u, min(f, cap[i]), lvl, it)
if d:
cap[i] -= d; cap[i ^ 1] += d
return d
it[v] += 1
return 0
cost = 0
while True:
lvl = bfs()
if lvl[n] < 0:
break
it = [0] * (n + 1)
while True:
d = dfs(1, float("inf"), lvl, it)
if not d:
break
cost += d
roads = [i + 1 for i in range(m) if (lvl[to[2 * i + 1]] >= 0) != (lvl[to[2 * i]] >= 0)]
print("cost", cost)
print("close:" + "".join(" " + str(r) for r in roads))
main()
cost 6
close: 4 6 8