Chapter 12 · Cuts and Flows
Max Flow: Ford–Fulkerson, Dinic, Push–Relabel
Three augmenting strategies, why each terminates, Dinic's O(V^2 E) proof, and how to read the min cut out of the residual graph.
While a path s ⇝ t exists in the residual graph Gf, take one and push the bottleneck capacity along it. The flow stays feasible, strictly increases, and stops exactly when no such path exists.
If capacities are integral, the algorithm terminates with a maximum flow, and |f| = c(S,bar S) where S is the set of vertices reachable from s in the final Gf.
Each augmentation increases |f| by at least 1 (integral bottlenecks), and |f| ≤ ∑v c(s,v) bounds it above — so it terminates. At termination S is well defined and t ∉ S. Every edge out of S is saturated (else its head would be reachable), and every edge into S carries zero flow (else the reverse residual edge would make its tail reachable). Hence
and weak duality (Cuts and Flows) then makes f maximum and (S,bar S) minimum. ∎
#Three ways to pick the path
| algorithm | choice | bound | practical |
|---|---|---|---|
| Ford–Fulkerson (DFS) | arbitrary | O(|f| · E) — unbounded with irrational capacities | never use; can be exponentially slow with "bad" paths |
| Edmonds–Karp | shortest (BFS) | O(V E2) | reliable, V E2 up to a few 107 |
| Dinic | blocking flow in the level graph | O(V2 E), O(E√V) unit-capacity, O(V2/3E) unit-network | the default; usually 10–100× the bound |
| Push–relabel (FIFO/highest) | local saturate + relabel | O(V2√E) with gap+global relabel heuristics, O(V3) plain | fastest on dense graphs and on huge sparse ones with good heuristics |
struct Edge { int to, rev, cap; };
vector<vector<Edge>> g(n);
void add(int u, int v, int cap) { // residual pair: forward cap, backward 0
g[u].push_back({v, (int)g[v].size(), cap});
g[v].push_back({u, (int)g[u].size() - 1, 0});
}
int lvl[n], it[n];
bool bfs() {
fill(lvl, lvl + n, -1); queue<int> q{ }; lvl[s] = 0; q.push(s);
while (q.size()) {
int v = q.front(); q.pop();
for (auto &e : g[v]) if (e.cap && lvl[e.to] < 0) { lvl[e.to] = lvl[v] + 1; q.push(e.to); }
}
return lvl[t] >= 0;
}
int dfs(int v, int pushed) { // blocking flow, one DFS "cursor" per vertex
if (v == t) return pushed;
for (int &cid = it[v]; cid < (int)g[v].size(); cid++) {
Edge &e = g[v][cid];
if (e.cap && lvl[e.to] == lvl[v] + 1) {
int tr = dfs(e.to, min(pushed, e.cap));
if (!tr) continue;
e.cap -= tr; g[e.to][e.rev].cap += tr;
return tr;
}
}
return 0;
}
long long flow = 0;
while (bfs()) {
fill(it, it + n, 0);
while (int pushed = dfs(s, INF)) flow += pushed;
}Each phase (one BFS + one blocking flow) costs O(VE), and there are at most V-1 phases.
The blocking flow computation is O(VE): every DFS either saturates an edge (at most E saturations) or advances a cursor it[v] permanently (at most V+E cursor steps per unit... formally, the total number of dfs calls that return 0 is bounded by the number of cursor advances, O(VE) including the path lengths). For the phase count: after a phase, the shortest augmenting-path length strictly increases (a standard argument: any new residual s–t path must use a backward edge of the blocking flow, which skips at least one level, so its length grows), and lengths are at most V-1. ∎
How the min cut is read off
- run to completion, then BFS from s in the residual graph → S; the cut edges are the original edges from S to bar S,
- "which vertices can be on the source side of some min cut?" — the family of min cuts forms a lattice; contract strongly-connected components of the final residual graph, and the min cuts correspond to closed sets of the condensation that contain scc(s) and exclude scc(t): a vertex is in all min cuts' source sides iff scc(s) reaches it, in none iff it reaches scc(t),
- minimum number of edges to delete to separate s,t = max flow with unit capacities (Menger again, Connectivity, Bridges, Articulation Points), and the deletion set is the cut's forward edges.
Dinic's level graph: grey edges are unusable (wrong level), green carries the blocking flow. Watch the phase count on the pathological graph — the level of t rises by one each phase, which is the V-1 bound being tight.
Maintain a pre-flow (excess allowed at internal vertices) and heights h with h(s)=n, h(t)=0, and the validity condition h(u) ≤ h(v)+1 for every residual edge. Push along admissible edges (h(u) = h(v)+1) as much as capacity allows; relabel a vertex with excess by setting h(u) = 1 + min h(v) over residual out-edges. Termination: no excess outside s,t ⇒ a valid flow; maximality: h(u) ≥ n marks "u cannot reach t", and {u : h(u) ≥ n} is a min cut's source side. With highest-label selection + gap relabelling + periodic global relabel (BFS backwards from t in the residual graph), it is the fastest known in practice for dense/large networks.
- Use
long longfor capacities and the answer;intoverflows at 2×109, and summing 1000 edges of 109 out of s is a standard WA, - parallel edges: merge them or (easier) let the adjacency list hold several
Edges — Dinic handles it, butcap[u][v] = cin a matrix overwrites; CSES Download Speed tests exactly this, - anti-parallel edges (u → v and v → u both exist): you cannot use the "reverse edge index" trick naively — store
revper edge as above and it works, but a matrix implementation double-counts, - recursion depth in
dfsis O(V): fine at 2×105 with care, addit-based iteration or an explicit stack if V = 106.