Dinic
A layered-network max-flow algorithm that is fast enough for most contest flow models and reusable in many reductions.
Dinic
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Dinic is the max-flow algorithm I expect to implement in contests unless the graph is tiny or the reduction is very specialized. It is general, predictable, and usually fast enough for the standard modeling problems built on source, sink, capacities, and cut arguments.
When to Use It
Use Dinic when:
the problem can be modeled as moving as much flow as possible through a capacitated network,
you need edge-disjoint or vertex-disjoint path style reasoning,
the graph is too large for a naive augmenting-path implementation.
Typical reductions include bipartite matching, task assignment with capacities, cut separation, and path packing.
Core Idea
Dinic alternates between two steps:
run BFS from the source to build a level graph,
run DFS only along edges that go one level deeper, pushing a blocking flow.
The level graph ensures that DFS only explores shortest augmenting paths in the current residual network.
Key Insight
One BFS groups many augmenting paths together. Instead of finding and using only one path, Dinic pushes a whole blocking flow before rebuilding levels. That is why it is much faster than plain Ford-Fulkerson with arbitrary paths.
Operations / Main Technique
add a directed edge plus its residual reverse edge,
BFS to compute levels,
DFS with current-edge pointers to avoid rescanning dead edges,
repeat until the sink becomes unreachable.
Worked example.
In a bipartite matching reduction, the BFS builds layers \(s \to\) left part \(\to\) right part \(\to t\). The DFS then pushes multiple augmenting paths through that layered structure before the next BFS is needed.
Correctness Intuition
Every DFS push follows a valid residual path and preserves flow conservation. When the blocking flow step ends, every source-to-sink path in the current level graph contains a saturated edge, so no more shortest augmenting paths remain. If BFS later cannot reach the sink, the residual network has no augmenting path at all, so the current flow is maximum.
Complexity Analysis
The general bound is \(O(V^2 E)\), with much better behavior on many contest graph families. In practice Dinic is the standard max-flow baseline for sparse graphs.
Implementation
The code uses:
adjacency lists of residual edges,
level BFS,
DFS with iterator pointers,
64-bit capacities.
Common Pitfalls
Forgetting the reverse edge or updating the wrong reverse index.
Using 32-bit capacities when the modeled totals are large.
Omitting the current-edge pointer and then rescanning too much.
Building the graph correctly but forgetting vertex-splitting when vertex capacities matter.
Variants / Extensions
Bipartite matching as a unit-capacity flow problem.
Lower-bound flow and circulation reductions.
Dinic on graphs with vertex capacities via node splitting.
Practice Problems
Maximum bipartite matching by max flow.
Edge-disjoint paths between two vertices.
Minimum cut partition after computing a max flow.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Dinic {
struct Edge {
int to;
int rev;
long long cap;
};
int n;
vector<vector<Edge>> graph;
vector<int> level;
vector<int> ptr;
explicit Dinic(int n) : n(n), graph(n), level(n), ptr(n) {}
void add_edge(int u, int v, long long cap) {
Edge a{v, (int)graph[v].size(), cap};
Edge b{u, (int)graph[u].size(), 0};
graph[u].push_back(a);
graph[v].push_back(b);
}
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 (const Edge& e : graph[v]) {
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
long long dfs(int v, int t, long long pushed) {
if (v == t || pushed == 0) {
return pushed;
}
for (int& cid = ptr[v]; cid < (int)graph[v].size(); ++cid) {
Edge& e = graph[v][cid];
if (e.cap == 0 || level[e.to] != level[v] + 1) {
continue;
}
long long flow = dfs(e.to, t, min(pushed, e.cap));
if (flow == 0) {
continue;
}
e.cap -= flow;
graph[e.to][e.rev].cap += flow;
return flow;
}
return 0;
}
long long max_flow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, t, (long long)4e18)) {
flow += pushed;
}
}
return flow;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.