Maximum flow (Dinic)
The maximum flow from to and, from the last BFS, a minimum cut. Bipartite matching and disjoint paths build on it.
When
The signal is usually indirect: "the maximum number of pairs", "the minimum number of roads to close so that you cannot get from to ", "how many routes with no common edge". With up to a few hundred or thousand, flow is often the answer.
The idea
Every edge has a capacity and a reverse edge with capacity 0. When you push flow along an edge, its capacity drops by and the reverse edge's grows by . A later path can thus "take back" flow that was sent the wrong way.
Dinic works in phases:
- BFS from in the residual graph: every vertex gets a level.
- DFS that uses only edges from level to , until no more flow fits (blocking flow). The pointer
it[u]remembers which edge to continue from, so an edge that has "died" is not looked at again in the same phase.
The distance of grows strictly in every phase, so there are at most phases. Overall in the worst case, for bipartite matching. In practice it is much faster.
Minimum cut. When it finishes, the vertices reached by the last BFS (level != -1) form the side of . The edges from them to the rest are a minimum cut, and its capacity equals the flow (max-flow min-cut theorem). The test verifies both, comparing against an enumeration of all cuts.
Three problems, one construction
Download Speed: the flow itself.Police Chase: the minimum cut, with capacity 1 per road in both directions.School Dance: source → boys (1), boy → girl (1), girls → sink (1). The flow is the maximum matching; the pairs are the boy → girl edges with saturated capacity.
Pitfalls
- Undirected edge: two
addEdgecalls, one per direction. - The DFS is recursive, but its depth is at most the distance of , i.e. . For the sizes where flow is the right choice, that is safe.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Maximum flow, Dinic's algorithm. O(V^2 E) in general, O(E sqrt V) for bipartite matching.
// BFS builds the level graph; DFS sends blocking flow along edges with level[v] = level[u] + 1.
// it[u] remembers the next edge to try, so dead edges are not scanned twice in one phase.
// After maxFlow, the vertices with level != -1 form the source side of a minimum cut.
struct Dinic {
struct Edge {
int to;
ll cap;
};
int n;
vector<Edge> edges;
vector<vector<int>> g;
vector<int> level;
vector<int> it;
Dinic(int vertices) : n(vertices), g(vertices), level(vertices), it(vertices) {}
// Edge i and its reverse i ^ 1 are stored next to each other.
void addEdge(int u, int v, ll cap) {
g[u].push_back(edges.size());
edges.push_back({v, cap});
g[v].push_back(edges.size());
edges.push_back({u, 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 u = q.front();
q.pop();
for (int id : g[u]) {
if (edges[id].cap > 0 && level[edges[id].to] == -1) {
level[edges[id].to] = level[u] + 1;
q.push(edges[id].to);
}
}
}
return level[t] != -1;
}
ll dfs(int u, int t, ll pushed) {
if (u == t) {
return pushed;
}
for (; it[u] < (int)g[u].size(); it[u]++) {
int id = g[u][it[u]];
int v = edges[id].to;
if (edges[id].cap > 0 && level[v] == level[u] + 1) {
ll got = dfs(v, t, min(pushed, edges[id].cap));
if (got > 0) {
edges[id].cap -= got;
edges[id ^ 1].cap += got;
return got;
}
}
}
return 0;
}
ll maxFlow(int s, int t) {
ll flow = 0;
while (bfs(s, t)) {
fill(it.begin(), it.end(), 0);
while (true) {
ll f = dfs(s, t, LLONG_MAX);
if (f == 0) {
break;
}
flow += f;
}
}
return flow;
}
};
Tested on 1,500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Download Speed · Graph Algorithms
- Police Chase · Graph Algorithms
- School Dance · Graph Algorithms
- Distinct Routes · Graph Algorithms
More in the USACO Guide
- Maximum Flow · usaco.guide/adv/max-flow
In English, with more problems per level.