Why this matters when you build with AI
A maximum flow problem asks how much can go from a source s to a sink t when every edge has a capacity. It shows up in disguise: how many matches a set of workers can be given, how many packets a network can carry, how to cut the fewest edges to separate two groups. AI tools often answer these with a greedy rule, such as "send along any path with room, and stop when none is left". That rule is wrong, and the mistake is quiet. The answer is a number that looks plausible.
Ask a model for "max flow on a 500-node graph" and you will often get a Ford-Fulkerson loop that finds a path with depth-first search and pushes its bottleneck. It has three typical faults. It has no reverse edges, so it cannot undo a bad early choice. It searches with no level rule, so it may choose long paths that block short ones. Or it rescans the same dead edges every time, which is slow on large graphs.
Dinic's algorithm fixes all three. You catch its mistakes by comparing with a slow solver that is obviously right, on many small random graphs. This lesson builds Dinic, shows each step on a small network with real output, and then runs the comparison.
A prompt that states the limits and the output you need:
Write C++17 for maximum flow with up to 200 vertices and 5000 edges, capacities up to 10^9.
Use Dinic's algorithm with a residual graph, BFS levels, and a DFS that uses current-arc pointers.
Use long long for flow. Say how deep the recursion can go on a path-shaped graph.
Return the max flow value and the set of vertices reachable from the source after the last phase.
Say the worst-case bound in your own words and say which of your claims you did not test.A good answer has a reverse edge for every edge, resets the current-arc pointers at the start of each phase, uses long long, and returns the source side of the min cut. Check it by reading the DFS loop and by running it on the test in the hands-on section. A weak answer has no reverse edges, uses int, or claims a bound without saying which case it covers.
Terms used
- A flow network is a directed graph where each edge
u -> vhas a capacity, a limit on how much can go along it. Two special vertices are the sourcesand the sinkt. - A flow assigns a number to each edge, with 0 at most the flow and at most the capacity. For every vertex other than
sandt, the flow in equals the flow out. The value of a flow is the total that leavess. - The residual graph shows what can still change. Each edge with capacity
cand flowfleaves a forward residual ofc - fin its direction, and a backward residual offin the opposite direction. - An augmenting path is a path from
stotin the residual graph. Pushing the smallest residual on it increases the flow by that amount. - A level graph keeps only the edges that go from a vertex at BFS distance
kto one at distancek + 1, measured fromsin the residual graph. - A blocking flow is a flow that saturates at least one edge on every shortest path in the level graph. After it, the distance from
stotstrictly grows. - A current-arc pointer, written
it[v], remembers the next edge ofvto try. An edge that failed once in a phase will fail again in that phase, so the pointer never goes back. - A cut is a split of the vertices into a side with
sand a side witht. Its capacity is the total capacity of the edges that go from thesside to thetside. The minimum cut has the smallest such total.
The idea: send flow, then undo a bad choice
Here is a small network with a source, a sink, and four vertices in between. Think of it as a courier company that moves parcels per hour from a depot (vertex 0) to a station (vertex 5) through hubs 1 to 4.
0 -> 1 (4) 0 -> 2 (3) 1 -> 2 (2) 1 -> 3 (3)
2 -> 4 (4) 3 -> 4 (1) 3 -> 5 (2) 4 -> 5 (3)The number in brackets is the capacity. One way to send parcels is to take any path from 0 to 5 and push as much as the smallest capacity on it allows. Take 0 -> 1 -> 3 -> 5. The smallest capacity is 2 (edge 3 -> 5), so push 2. Now 3 -> 5 is full. Next take 0 -> 2 -> 4 -> 5, with smallest capacity 3 (edge 4 -> 5), so push 3. Total so far: 5. No path is left, so 5 is the answer here.
That worked, but a greedy choice can be wrong. Take this network with five edges, all capacity 1, from s to t:
s -> a, s -> b, a -> b, a -> t, b -> tSuppose the first path found is s -> a -> b -> t. It pushes 1 and fills a -> b and b -> t. The other path, s -> b -> ... , now has nowhere to go, because b -> t is full. A plain search stops at 1. The right answer is 2: s -> a -> t and s -> b -> t.
The fix is the reverse edge. The path s -> a -> b -> t put 1 unit on a -> b, so the residual graph has 1 unit of backward room on b -> a. The next search can use s -> b -> a -> t. That path cancels the flow on a -> b and sends that unit to a -> t instead. The net effect is flow 2. This is why every edge gets a partner in the residual graph, as in the code below (e[id ^ 1]). The partner starts with capacity 0 and gains capacity when flow goes forward.
Without reverse edges a search can only add flow, never move it. With them, a later path can undo part of an earlier one. That is the whole idea of augmenting paths.
Level graphs: shortest paths first
Plain augmenting paths can be long, and long paths use up edges that short paths need. Dinic's rule: in each phase, use only shortest paths.
A phase has two steps.
- Run BFS from
son the residual graph with positive capacity. Each vertex gets a level, its BFS distance. Ifthas no level, stop. - Find a blocking flow in the level graph, which keeps only edges that go from level
kto levelk + 1.
After a phase, the distance from s to t in the residual graph is strictly larger than before. Distances are at most the number of vertices, so there are at most that many phases. This is why Dinic's method is faster than picking arbitrary paths.
Worked trace on the courier network. BFS from vertex 0 gives these levels (this is the output of demo_phases.cpp in my scratch folder):
phase 1 level: 0=0 1=1 2=1 3=2 4=2 5=3The level graph keeps 0->1, 0->2, 1->3, 2->4, 3->5 and 4->5. It drops 1->2 and 3->4, because both ends sit on the same level (1 and 1, or 2 and 2). The DFS then works like this:
- From 0, try edge 0 -> 1 (level 1). From 1, try 1 -> 2 first: it is in the list of edges of 1, but level 2 is not 1 + 1, so skip it. Try 1 -> 3: level 2, good. From 3, try 3 -> 4: same level, skip. Try 3 -> 5: level 3, good, capacity 2. Push 2. Edge 3 -> 5 is now full.
- Back at 1, the edge 1 -> 3 has 1 unit of room left, but 3 has nothing more to offer. Vertex 1 has no other usable edge, so it returns 2 and marks itself done for this phase.
- Back at 0, the edge 0 -> 1 has room, but 1 is done. Try 0 -> 2 (level 1). From 2, the edge 2 -> 4 goes to level 2. From 4, the edge 4 -> 5 goes to level 3 with capacity 3. Push 3.
- Total for this DFS from 0: 2 + 3 = 5.
The program prints a single line for this DFS, blocking path flow 5, because one DFS call from the source returns the total it pushed. The internal split is the one in steps 1 to 4.
A second BFS would find no path, so the algorithm stops with flow 5. The final output is:
phase 1 total pushed 5, running flow 5
max flow 5
min cut source side: 0 1 2 3 4Blocking flow with current-arc pointers
A naive DFS in a level graph can rescan the same edges many times. Say a vertex v has 1000 outgoing edges and 1000 units arrive at v one at a time. Without memory, each arrival scans all of them. The current-arc pointer it[v] solves this. It starts at the first edge of v for each phase, and it only moves forward. When an edge is full, or when the vertex beyond it is a dead end, the pointer moves past that edge for good.
The code below uses one more trick: a DFS call pushes as much as it can from v, not just one path. It passes the room still available (f - pushed) to each child and stops early when pushed == f. When it stops early, it does not advance the pointer, because the edge may still have room.
Here is the full structure in dinic.hpp. It is the code I compiled and tested.
#pragma once
#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
// Dinic's maximum flow. Capacities are long long. Edges are stored in pairs:
// edge id e and its reverse edge id e ^ 1 (the reverse starts with capacity 0).
struct Dinic {
struct Edge {
int to;
long long cap; // remaining (residual) capacity
};
int n;
std::vector<Edge> e;
std::vector<std::vector<int>> g; // g[v] = ids of edges leaving v
std::vector<int> level, it;
explicit Dinic(int n) : n(n), g(n), level(n), it(n) {}
// Adds u -> v with capacity c. Returns the id of the forward edge.
int add_edge(int u, int v, long long c) {
int id = static_cast<int>(e.size());
e.push_back({v, c});
g[u].push_back(id);
e.push_back({u, 0});
g[v].push_back(id + 1);
return id;
}
// Flow that went through forward edge id: the reverse edge's capacity.
long long flow_on(int id) const { return e[id ^ 1].cap; }
// BFS on the residual graph. Sets level[v] = distance from s, or -1.
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v]) {
if (e[id].cap > 0 && level[e[id].to] < 0) {
level[e[id].to] = level[v] + 1;
q.push(e[id].to);
}
}
}
return level[t] >= 0;
}
// Pushes up to f from v to t along level-increasing edges.
// it[v] is the current-arc pointer: edges before it[v] are dead for this phase.
long long dfs(int v, int t, long long f) {
if (v == t) return f;
long long pushed = 0;
for (int& i = it[v]; i < static_cast<int>(g[v].size()); ++i) {
int id = g[v][i];
int to = e[id].to;
if (e[id].cap > 0 && level[to] == level[v] + 1) {
long long d = dfs(to, t, std::min(f - pushed, e[id].cap));
if (d > 0) {
e[id].cap -= d;
e[id ^ 1].cap += d;
pushed += d;
if (pushed == f) return pushed; // edge i may still have room: do not advance
}
}
}
return pushed;
}
long long max_flow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
std::fill(it.begin(), it.end(), 0);
while (long long f = dfs(s, t, LLONG_MAX)) flow += f;
}
return flow;
}
// After max_flow: vertices reachable from s in the residual graph (the source side of a min cut).
std::vector<bool> source_side(int s) {
std::vector<bool> seen(n, false);
std::queue<int> q;
seen[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : g[v]) {
if (e[id].cap > 0 && !seen[e[id].to]) {
seen[e[id].to] = true;
q.push(e[id].to);
}
}
}
return seen;
}
};The program that reads a network and prints the flow is short:
// Reads: n m s t, then m lines "u v c". Prints the max flow.
#include <cstdio>
#include "dinic.hpp"
int main() {
int n, m, s, t;
if (scanf("%d %d %d %d", &n, &m, &s, &t) != 4) return 0;
Dinic d(n);
for (int i = 0; i < m; ++i) {
int u, v;
long long c;
if (scanf("%d %d %lld", &u, &v, &c) != 3) return 0;
d.add_edge(u, v, c);
}
printf("%lld\n", d.max_flow(s, t));
return 0;
}Reading the min cut
After the last BFS fails, the vertices with a level form the source side of a minimum cut. In the courier network they are 0, 1, 2, 3 and 4. The edges that leave that set and reach vertex 5 are 3 -> 5 (capacity 2) and 4 -> 5 (capacity 3). Their total is 5, the same as the flow. That equality is the max-flow min-cut theorem: the largest flow equals the smallest cut.
The source_side method finds the same set by a search in the residual graph. It is the tool you use in the matching and project-selection lessons (the next lesson in this module), because the chosen set is exactly the source side of the cut.
Complexity
- Phases: at most
V - 1, because the distance fromstotgrows each phase. - Blocking flow in one phase:
O(V E)with current-arc pointers. Each edge is advanced past at most once per phase, and each push costs at most one path length. - General capacities:
O(V^2 E)in total. This is the standard bound for Dinic. Real inputs are usually much faster. - Unit capacities (every edge has capacity 1, as in matching): the known bound is
O(E * min(sqrt(E), V^(2/3))). I did not re-derive it. Even and Tarjan, "Network flow and testing graph connectivity", SIAM Journal on Computing, 1975, is the paper usually cited for it. I did not open that paper, so treat the citation as a pointer to check. - Memory:
O(V + E).
What I checked here: the code and the bounds in the list above. I did not run a timing study for general capacities. On this machine (WSL2, g++ 15.2.0, -O2), a random bipartite matching with 20000 vertices on each side and 100000 edges took 0.19 s wall time, but that run included the Hopcroft-Karp matching and the cut check as well. It is a sanity check, not a benchmark.
Worked original problem: the courier network
Problem. A depot sends parcels to a station through hubs. Each road has a capacity in parcels per hour. Find the largest number of parcels per hour that can reach the station. Then say which roads limit it.
Input (roads listed as u v capacity, vertex 0 is the depot, vertex 5 is the station):
6 8 0 5
0 1 4
0 2 3
1 2 2
1 3 3
2 4 4
3 4 1
3 5 2
4 5 3Full solution: run the dinic program above on this input. Its output is:
5Then read the cut. The limiting roads are 3 -> 5 (capacity 2) and 4 -> 5 (capacity 3), which add up to 5. Upgrading road 0 -> 1 from 4 to 5 changes nothing, because the cut does not use it. Raising 3 -> 5 from 2 to 3 raises the answer to 6: then 0 -> 1 -> 3 -> 5 carries 3 and 0 -> 2 -> 4 -> 5 carries 3. A learner who answers "upgrade the widest road" has not read the cut. The lesson point is that only roads in the minimum cut limit the answer.
The phase trace in the earlier section comes from the same network with a small extra program that prints levels. Its output is the three lines shown there.
Common mistakes
No reverse edges, or a reverse edge with the wrong capacity. Symptom: the answer is too small on networks where the first path blocks a better one. On the 5-edge network from the idea section, a search that follows the path s -> a -> b -> t first and never uses the backward room on b -> a returns 1 where the answer is 2. The reverse edge must start at capacity 0 for a directed edge.
Undirected edges added as one arc. Symptom: the answer is 0 when it should be positive. Take a single road between 0 and 1 with capacity 4, written as 1 0 4, with source 0 and sink 1. A directed arc 1 -> 0 gives flow 0. For an undirected road, add the edge and then set the reverse capacity to the same value: int id = d.add_edge(u, v, c); d.e[id ^ 1].cap = c;. The program in the scratch folder does this, and on the test above it prints 4. The directed version prints 0.
Current-arc pointers reset in the wrong place. Symptom: the program still gives the right answer on small tests but runs many more phases than expected. Reset it once per phase, after the BFS, not once per DFS call and not never.
Using int for capacities. Symptom: the answer wraps around or goes negative on large inputs. Three capacities of 10^9 sum to 3 * 10^9, which is above the largest 32-bit signed integer, about 2.1 * 10^9. Use long long for capacities and flow.
Reading flow from the wrong number. Symptom: a flow of 3 is printed as 1. After the run, the residual capacity of a forward edge is what is left, not what was sent. The flow on forward edge id is flow_on(id), which reads the reverse edge.
Deep recursion. Symptom: a crash on a long path graph with about 10^5 vertices. The DFS recurses once per level. On a judge or in a contest, either raise the stack limit, or write the DFS with an explicit stack. This lesson keeps recursion to show the structure.
Using INF that is too small. Symptom: a cut that should be infinite is not, so the answer is too large. This matters in the next lesson, where infinite edges force choices. Choose INF larger than the sum of all finite capacities, and keep it in long long.
Hands-on exercise on your machine
Create a folder and copy dinic.hpp and the reader program above into it. Save the courier input as courier.txt. Then run:
g++ -std=c++17 -O2 -Wall -Wextra -o dinic dinic_main.cpp
./dinic < courier.txtThe output should be 5. Next, write a random test. Save this as brute_flow.py (it is the simple augmenting-path solver that the test compares against):
# Simple augmenting-path max flow (BFS, Edmonds-Karp) on an adjacency matrix.
import sys
from collections import deque
def max_flow(n, s, t, cap):
flow = 0
while True:
par = [-1] * n
par[s] = s
q = deque([s])
while q and par[t] == -1:
v = q.popleft()
for w in range(n):
if par[w] == -1 and cap[v][w] > 0:
par[w] = v
q.append(w)
if par[t] == -1:
return flow
b = float("inf")
w = t
while w != s:
b = min(b, cap[par[w]][w])
w = par[w]
w = t
while w != s:
cap[par[w]][w] -= b
cap[w][par[w]] += b
w = par[w]
flow += b
if __name__ == "__main__":
data = sys.stdin.read().split()
n, m, s, t = map(int, data[:4])
cap = [[0] * n for _ in range(n)]
k = 4
for _ in range(m):
u, v, c = int(data[k]), int(data[k + 1]), int(data[k + 2])
k += 3
cap[u][v] += c
print(int(max_flow(n, s, t, cap)))Then write a generator and a comparison loop in Python. The generator makes n between 2 and 9, m between 1 and 25 random edges with capacity 0 to 12, source 0 and sink n - 1. The loop runs both programs on 1000 seeds and counts disagreements. A correct run prints mismatches=0. My run with 3000 seeds gave tests=3000 mismatches=0. Your run should also print zero mismatches.
Prompt to use with an AI tool, after you have the code:
Here is my Dinic implementation (dinic.hpp) and a brute-force Edmonds-Karp solver.
Write a random test generator with n between 2 and 9, edges with capacities 0 to 12,
and compare the two on 1000 seeds. Print the first 3 disagreements with their seed.
Do not change either solver. Then list one input you think is hard for the greedy search
and say whether my code handles it, with the reason.A good answer keeps both solvers unchanged, uses a fixed seed per test, and prints the seed so a failure can be replayed. A weak answer changes the solver to make the test pass, or uses one fixed graph and calls it random.
Checklist
- Each edge has a reverse edge with capacity 0 (or the stated capacity for undirected edges).
- Levels come from a BFS on the residual graph, and the DFS uses only edges with level increased by 1.
itis reset to 0 after each BFS, once per phase.- Capacities and flow are
long long, andINFis larger than any finite cut. - The answer is checked against a slow solver on random small inputs, not only on the sample.
- The min cut is the set reachable from
sin the residual graph, and its capacity equals the flow. - Recursion depth is known for the largest input, or the DFS is iterative.
Summary
A flow is a way to send things from s to t within capacities. A residual graph shows the room left in each direction, and the reverse edges let a later path undo an earlier choice. Dinic repeats two steps: BFS levels, then a blocking flow with current-arc pointers. The set of vertices reachable from s at the end is the source side of a min cut. Test the code against an augmenting-path solver before trusting it.
Practice
Practice 1. A network has vertices 0 to 3, source 0, sink 3, and edges 0 1 3, 0 2 2, 1 2 5, 1 3 2, 2 3 3, where each line is u v capacity. Find the max flow by hand. Then list the level of every vertex in the first BFS.
Hint: the answer is at most the total capacity of edges leaving s, and also at most the total capacity of edges entering t. Find a cut with that value.
Show the answer
The max flow is 5. A cut that achieves it has 0, 1 and 2 on the source side, with edges 1 -> 3 (capacity 2) and 2 -> 3 (capacity 3). The first BFS gives levels 0 = 0, 1 = 1, 2 = 1, 3 = 2. The first phase pushes 2 along 0 -> 1 -> 3, then 2 along 0 -> 2 -> 3. The second phase pushes 1 along 0 -> 1 -> 2 -> 3, using the new room on 1 -> 2 and the 1 unit left on 2 -> 3. Total 5. After phase 2 no path is left, so the flow is 5 and two phases pushed flow.
Practice 2. A road between vertices 0 and 1 has capacity 4, and it is written as the line 1 0 4. The source is 0 and the sink is 1. Give the answer for an undirected road and for a single arc from 1 to 0. Then say what the input line must become in the code.
Hint: the directed arc only goes one way. The source is at vertex 0 and must send to vertex 1.
Show the answer
The undirected road gives 4. A single arc 1 -> 0 gives 0, because no edge leaves vertex 0. In code, add the edge with add_edge(1, 0, 4) and then set the reverse capacity: int id = d.add_edge(1, 0, 4); d.e[id ^ 1].cap = 4;. The scratch test prints 4 for the undirected version and 0 for the directed one.
Practice 3. Using the courier network from this lesson, list the edges that go into vertex 5 and give their total capacity. Then add an edge 2 -> 5 with capacity 1 and find the new max flow.
Hint: the total into vertex 5 is a cut with s on the other side. For the new flow, look for a path that goes through edge 1 -> 2, which has unused room.
Show the answer
The edges into 5 are 3 -> 5 (capacity 2) and 4 -> 5 (capacity 3). Their total is 5, which matches the flow. With the new edge 2 -> 5 (capacity 1), the flow rises to 6. One way to get there: push 1 along 0 -> 1 -> 2 -> 5. Edge 0 -> 1 has 2 units left, edge 1 -> 2 has 2 units unused, and the new edge has 1. The source side now has three edges into 5, with total capacity 6, so 6 is the largest possible flow.
Practice 4. Write a function flows_on_forward_edges that takes a Dinic after max_flow and returns the flow on each forward edge, given the list of forward edge ids returned by add_edge.
Hint: the flow on an edge is stored on its reverse edge.
Show the answer
std::vector<long long> flows_on_forward_edges(const Dinic& d, const std::vector<int>& ids) {
std::vector<long long> out;
out.reserve(ids.size());
for (int id : ids) out.push_back(d.flow_on(id));
return out;
}Practice 5. Explain in two sentences why a blocking flow leaves no path of the current level length, and why the next BFS distance is strictly larger.
Hint: a path of the current length uses only level-increasing edges. Ask what happens to the edges it uses.
Show the answer
Every shortest path in the level graph uses an edge that is now full, so the level graph cannot give that path again. Any path left in the residual graph must use an edge that does not go one level up, so it is longer than the current distance.