Max Flow
Water flows through pipes. Data moves through network links. Cars drive on roads. All these systems have capacity constraints and a natural question: what's the maximum throughput from point A to point B? That question is max flow, and Dinic's algorithm answers it fast enough for competitive programming.
The Max Flow Problem
You have a directed graph where each edge has a capacity -- the maximum amount of flow it can carry. Two special nodes: a source \(s\) (flow originates here) and a sink \(t\) (flow terminates here). Find the maximum total flow from \(s\) to \(t\) such that:
- Capacity constraint: flow on edge \((u, v) \le\) capacity of \((u, v)\).
- Flow conservation: for every node except \(s\) and \(t\), flow in = flow out.
The Residual Graph
The residual graph is the key data structure. For each edge \((u, v)\) with capacity \(c\) and current flow \(f\):
- Forward edge \((u, v)\) with residual capacity \(c - f\). You can push more flow.
- Backward edge \((v, u)\) with residual capacity \(f\). You can "undo" flow.
Backward edges are what make the algorithm correct. Without them, a greedy approach can get stuck at a suboptimal flow.
Key insight. The backward edge doesn't mean flow physically reverses. It means: "if I sent flow along this edge and later realize it was a mistake, I can redirect that flow elsewhere." It's a bookkeeping trick that enables optimal solutions.
Ford-Fulkerson Method
Idea: repeatedly find an augmenting path from \(s\) to \(t\) in the residual graph. Push as much flow as possible along it. Repeat until no augmenting path exists.
If you find augmenting paths using BFS, this becomes Edmonds-Karp with time complexity \(O(VE^2)\).
while (augmenting path exists from s to t in residual graph):
bottleneck = min residual capacity along the path
for each edge on the path:
decrease forward residual by bottleneck
increase backward residual by bottleneck
total_flow += bottleneck
The problem with Edmonds-Karp: each BFS finds one path and pushes flow along it. In the worst case, you need \(O(VE)\) augmenting paths.
Dinic's Algorithm
Dinic's improves on Edmonds-Karp by finding multiple augmenting paths per BFS. It builds a level graph using BFS, then finds blocking flows using DFS.
Steps:
- BFS from \(s\). Assign levels: \(\text{level}[s] = 0\), \(\text{level}[v] = \text{level}[u] + 1\) for each edge \(u \to v\) with residual capacity \(> 0\).
- DFS from \(s\) to \(t\), only following edges where \(\text{level}[v] = \text{level}[u] + 1\). Push flow along the path found. Repeat DFS until no more paths exist (blocking flow).
- Repeat from step 1 until BFS can't reach \(t\).
The level graph ensures DFS makes progress toward \(t\) at every step. No wandering, no cycles.
struct Edge { int to, rev; long long cap; };
struct Dinic {
vector<vector<Edge>> graph;
vector<int> level, iter;
Dinic(int n) : graph(n), level(n), iter(n) {}
void addEdge(int from, int to, long long cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return level[t] >= 0;
}
long long dfs(int v, int t, long long pushed) {
if (v == t) return pushed;
for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
Edge& e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
long long d = dfs(e.to, t, min(pushed, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
long long maxflow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
fill(iter.begin(), iter.end(), 0);
long long d;
while ((d = dfs(s, t, LLONG_MAX)) > 0)
flow += d;
}
return flow;
}
};
Gotcha. The
iter[]array is critical. It remembers which edges have been fully explored during DFS. Without it, the DFS would re-examine dead-end edges, destroying the time complexity.
Trace: Dinic's on a Small Network
Edges: 0→1 (cap 10), 0→2 (cap 10), 1→2 (cap 1), 1→3 (cap 10), 2→3 (cap 10).
Phase 1: BFS. Levels: 0→0, 1→1, 2→1, 3→2.
Phase 1: DFS.
| DFS Call | Path | Bottleneck | Flow So Far |
|---|---|---|---|
| 1 | 0→1→3 | min(10, 10) = 10 | 10 |
| 2 | 0→2→3 | min(10, 10) = 10 | 20 |
| 3 | 0→1→2→3 | min(0, 1, 0) -- 0→1 has 0 residual. Dead end. | 20 |
Phase 2: BFS. Can't reach \(t\) from \(s\). Done. Max flow = 20.
Key insight. The edge 1→2 with capacity 1 is never used because both direct routes already saturate. In a different graph, cross-edges like this would allow rerouting flow for higher throughput.
CSES Download Speed
Problem. A network has \(N\) computers and \(M\) connections. Each connection has a bandwidth (capacity). Find the maximum data transfer rate from computer 1 to computer \(N\).
Direct application of Dinic's. Node 1 is the source, node \(N\) is the sink.
#include <bits/stdc++.h>
using namespace std;
struct Edge { int to, rev; long long cap; };
struct Dinic {
vector<vector<Edge>> graph;
vector<int> level, iter;
Dinic(int n) : graph(n), level(n), iter(n) {}
void addEdge(int from, int to, long long cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size()-1, 0});
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0; q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v])
if (e.cap > 0 && level[e.to] < 0)
level[e.to] = level[v]+1, q.push(e.to);
}
return level[t] >= 0;
}
long long dfs(int v, int t, long long f) {
if (v == t) return f;
for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
Edge& e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
long long d = dfs(e.to, t, min(f, e.cap));
if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; }
}
}
return 0;
}
long long maxflow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
fill(iter.begin(), iter.end(), 0);
long long d;
while ((d = dfs(s, t, LLONG_MAX)) > 0) flow += d;
}
return flow;
}
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
Dinic dinic(n + 1);
for (int i = 0; i < m; i++) {
int a, b; long long c;
scanf("%d%d%lld", &a, &b, &c);
dinic.addEdge(a, b, c);
}
printf("%lld\n", dinic.maxflow(1, n));
}
Complexity Comparison
| Algorithm | Time | When to Use |
|---|---|---|
| Edmonds-Karp (BFS) | \(O(VE^2)\) | Simple to implement, small graphs |
| Dinic's | \(O(V^2 E)\) | General purpose, competitive programming standard |
| Dinic's on unit-capacity graphs | \(O(E\sqrt{V})\) | Bipartite matching, special structure |
Dinic's is the go-to for competitive programming. Memorize the template. It handles everything from basic flow to bipartite matching to min-cut problems.
Gotcha. Parallel edges are fine. If there are two edges from \(u\) to \(v\) with capacities \(c_1\) and \(c_2\), add them as separate edges. Don't merge them -- the residual graph handles it correctly.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES Download Speed | cses.fi/problemset/task/1694 | Medium |