SyntaxPilot
Courses/Competitive Programming/Lesson 58
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 58 of 90

Max flow: Dinic's algorithm

queued

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

  1. BFS from the source over edges with room: lvl[v] = the fewest edges from s to v.
  2. Push only along edges with lvl[u] == lvl[v] + 1: every path is a shortest path in the residual graph.
  3. 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.
  4. 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, then close: 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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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 (19 vs 23); 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 (-2081215223 otherwise).
  • Max flow = min cut; the cut is read from lvl after 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