Network Flow (Max-Flow, Min-Cut, Bipartite Matching)
Table of Contents
Network flow models problems from transportation and logistics to bipartite matching and project selection. This guide covers Ford-Fulkerson, Edmonds-Karp, Dinic's, and applications like min-cut and bipartite matching.
Flow Networks -- Definitions and Concepts
What is a Flow Network?
A flow network is a directed graph G = (V, E) with two special vertices and a capacity function:
- Source (s): Where flow originates. Has no incoming edges (or we ignore them).
- Sink (t): Where flow is consumed. Has no outgoing edges (or we ignore them).
- Capacity c(u, v): The maximum amount of flow that can pass through edge (u, v). Always non-negative.
- Flow f(u, v): The actual amount of flow on edge (u, v).
Two Fundamental Constraints
Every valid flow must satisfy:
1. Capacity Constraint: For every edge (u, v):
0 <= f(u, v) <= c(u, v)
Flow cannot exceed capacity, and cannot be negative.
2. Flow Conservation: For every vertex v except s and t:
Sum of flow into v = Sum of flow out of v
What enters a node must leave it. No flow is created or destroyed at intermediate nodes.
The value of the flow |f| is the total flow leaving the source (equivalently, entering the sink).
The Residual Graph -- The Key Insight
The residual graph G_f is the most important concept in network flow. It tells us where we can push additional flow.
For each edge (u, v) with capacity c and current flow f:
- Forward edge (u -> v) with residual capacity
c - f(room to push more flow) - Backward edge (v -> u) with residual capacity
f(ability to "undo" existing flow)
The backward edges are the crucial insight. They allow algorithms to correct earlier decisions by effectively rerouting flow.
Why can't we just greedily push flow? Consider a diamond graph s -> A -> t and s -> B -> t with an edge A -> B. If we greedily send flow through s -> A -> B -> t, we might saturate A -> B and block the path s -> A -> t. The backward edge B -> A in the residual graph lets us fix this by "undoing" the A -> B flow and redirecting it through A -> t instead.
Augmenting Path
An augmenting path is any path from s to t in the residual graph. The bottleneck of the path is the minimum residual capacity along it. We can increase the total flow by the bottleneck amount by pushing flow along this path.
Finding and using augmenting paths:
1. Build residual graph from current flow
2. Find any s-t path in residual graph
3. Bottleneck = min residual capacity on path
4. Push 'bottleneck' units along the path:
- For forward edges: increase flow by bottleneck
- For backward edges: decrease flow by bottleneck
5. Repeat until no s-t path exists
Max-Flow Min-Cut Theorem
What is a Cut?
An s-t cut is a partition of V into two sets (S, T) where s is in S and t is in T. The capacity of the cut is the sum of capacities of edges going from S to T (not T to S).
The Theorem
Max-Flow Min-Cut Theorem: In any flow network, the maximum value of flow from s to t equals the minimum capacity of any s-t cut.
max |f| = min capacity(S, T)
over all s-t cuts
Proof Intuition
The proof has three parts:
-
Flow <= Cut (for any flow and any cut): Any flow must cross every cut. The flow across a cut cannot exceed the cut's capacity. So every cut gives an upper bound on the max flow.
-
When Ford-Fulkerson terminates: No augmenting path exists. Define S = vertices reachable from s in the residual graph, T = V - S. Since t is not reachable, (S, T) is a valid cut.
-
At termination, Flow = Cut: Every S-to-T edge is fully saturated (otherwise t would be reachable). Every T-to-S edge has zero flow (otherwise we'd have a backward residual edge). So the flow across this cut exactly equals the cut capacity.
Since Flow <= every Cut, and we found Flow = some Cut, this flow must be maximum and this cut must be minimum.
Finding the Min-Cut from Max-Flow
After computing max-flow:
- Build the final residual graph
- Run BFS/DFS from s to find all reachable vertices (set S)
- T = V - S
- The min-cut edges are all edges (u, v) where u is in S and v is in T
This is extremely useful in practice -- many problems ask for the min-cut, not the max-flow itself.
Ford-Fulkerson Method
The Algorithm
Ford-Fulkerson is a method (not a specific algorithm) because it doesn't specify how to find augmenting paths.
Ford-Fulkerson Method:
1. Initialize flow f(u,v) = 0 for all edges
2. While there exists an augmenting path p from s to t in residual graph G_f:
a. Find bottleneck = min residual capacity on p
b. For each edge (u,v) on p:
- If (u,v) is a forward edge: f(u,v) += bottleneck
- If (u,v) is a backward edge: f(v,u) -= bottleneck
3. Return total flow
Step-by-Step Walkthrough
Consider this graph:
Iteration 1: Find path s -> A -> C -> t
Bottleneck = min(10, 10, 10) = 10
Push 10 units. Total flow = 10.
Iteration 2: Find path s -> B -> D -> t
Bottleneck = min(10, 10, 10) = 10
Push 10 units. Total flow = 20.
No more augmenting paths. Max flow = 20.
This was the easy case. But what if DFS finds a bad path first?
What if DFS finds s -> A -> B -> D -> t first?
Bottleneck = min(10, 1, 10, 10) = 1
Push 1 unit. Total flow = 1.
Now the residual graph has backward edge B -> A with capacity 1.
Next path: s -> A -> C -> t
Bottleneck = min(9, 10, 10) = 9
Push 9 units. Total flow = 10.
Next path: s -> B -> D -> t
Bottleneck = min(10, 9, 10) = 9
Push 9 units. Total flow = 19.
Next path: s -> B -> A -> C -> t (uses backward edge B->A!)
Residuals: s->B has 1, B->A has 1 (backward), A->C has 1, C->t has 1
Bottleneck = 1
Push 1 unit. Total flow = 20.
Same answer! The backward edge fixed the suboptimal initial choice.
Why DFS Can Fail
With irrational capacities, DFS-based Ford-Fulkerson may not terminate and may even converge to a value less than the maximum flow. With integer capacities, it always terminates, but may take O(E * |f*|) time where |f*| is the max flow value -- exponentially bad if capacities are large.
Pathological example (integer but slow):
s ----(1000000)----> A ----(1000000)----> t
| ^| ^
| || |
|(1000000) (1)||(1) (1000000)
| || |
v |v |
s ----(1000000)----> B ----(1000000)----> t
If DFS alternates between s->A->B->t and s->B->A->t:
Each iteration pushes only 1 unit (bottleneck at A->B or B->A).
Takes 2,000,000 iterations instead of 2.
Complete C++ Implementation (DFS-based Ford-Fulkerson)
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev; // destination, index of reverse edge
int cap; // residual capacity
};
class FordFulkerson {
int n;
vector<vector<Edge>> graph;
vector<bool> visited;
void addEdgeInternal(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
// DFS to find augmenting path and push flow
int dfs(int v, int t, int pushed) {
if (v == t) return pushed;
visited[v] = true;
for (auto& e : graph[v]) {
if (!visited[e.to] && e.cap > 0) {
int d = dfs(e.to, t, min(pushed, e.cap));
if (d > 0) {
e.cap -= d; // reduce forward
graph[e.to][e.rev].cap += d; // increase backward
return d;
}
}
}
return 0;
}
public:
FordFulkerson(int n) : n(n), graph(n), visited(n) {}
void addEdge(int from, int to, int cap) {
addEdgeInternal(from, to, cap);
}
int maxFlow(int s, int t) {
int flow = 0;
while (true) {
fill(visited.begin(), visited.end(), false);
int pushed = dfs(s, t, INT_MAX);
if (pushed == 0) break;
flow += pushed;
}
return flow;
}
};
int main() {
// Graph: s=0, A=1, B=2, C=3, D=4, t=5
FordFulkerson ff(6);
ff.addEdge(0, 1, 10); // s -> A
ff.addEdge(0, 2, 10); // s -> B
ff.addEdge(1, 2, 1); // A -> B
ff.addEdge(1, 3, 10); // A -> C
ff.addEdge(2, 4, 10); // B -> D
ff.addEdge(3, 5, 10); // C -> t
ff.addEdge(4, 5, 10); // D -> t
cout << "Max flow: " << ff.maxFlow(0, 5) << endl;
// Output: Max flow: 20
}
Complexity:
- Time: O(E * |f*|) where |f*| is the max flow value. Each DFS is O(E), and each augmenting path increases flow by at least 1.
- Space: O(V + E) for the adjacency list representation.
When to use: Almost never in practice. Use Edmonds-Karp or Dinic's instead. Ford-Fulkerson is important conceptually but too slow for competitive programming.
Edmonds-Karp Algorithm
The Key Idea: BFS Instead of DFS
Edmonds-Karp is Ford-Fulkerson with one crucial change: always find the shortest augmenting path (fewest edges) using BFS. This simple change guarantees a polynomial time bound independent of the max flow value.
Why BFS Guarantees O(VE^2)
Theorem: Edmonds-Karp runs in O(VE^2) time.
Proof sketch:
- Each BFS augmentation takes O(E) time.
- The shortest path distance from s to any vertex v never decreases across iterations.
- After at most O(VE) augmentations, the algorithm terminates.
- Total: O(VE) augmentations * O(E) per BFS = O(VE^2).
Why O(VE) augmentations? Each augmentation saturates at least one edge (the bottleneck). An edge (u, v) can only become saturated again after v's distance from s increases by at least 2. Since distances are bounded by V, each edge is saturated O(V) times. Total saturations: O(VE).
Step-by-Step Walkthrough
BFS always finds the SHORTEST path (fewest edges).
Iteration 1: BFS finds s -> A -> C -> t (length 3)
Bottleneck = min(7, 5, 8) = 5
Push 5 units. Total flow = 5.
Residual: s->A:2, A->C:0, C->t:3, plus backward edges.
Iteration 2: BFS finds s -> B -> D -> t (length 3)
Bottleneck = min(4, 6, 5) = 4
Push 4 units. Total flow = 9.
Residual: s->B:0, B->D:2, D->t:1.
Iteration 3: BFS finds s -> A -> B -> D -> t (length 4)
Bottleneck = min(2, 3, 2, 1) = 1
Push 1 unit. Total flow = 10.
Iteration 4: No augmenting path exists.
Residual capacities: s->A:1, A->C:0 (saturated), D->t:0 (saturated).
BFS cannot reach t from s. Done!
Max flow = 10.
Complete C++ Implementation
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev;
int cap;
};
class EdmondsKarp {
int n;
vector<vector<Edge>> graph;
public:
EdmondsKarp(int n) : n(n), graph(n) {}
void addEdge(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
int maxFlow(int s, int t) {
int flow = 0;
while (true) {
// BFS to find shortest augmenting path
vector<int> parent(n, -1);
vector<int> parentEdge(n, -1);
queue<int> q;
parent[s] = s;
q.push(s);
while (!q.empty() && parent[t] == -1) {
int v = q.front(); q.pop();
for (int i = 0; i < (int)graph[v].size(); i++) {
Edge& e = graph[v][i];
if (parent[e.to] == -1 && e.cap > 0) {
parent[e.to] = v;
parentEdge[e.to] = i;
q.push(e.to);
}
}
}
if (parent[t] == -1) break; // no augmenting path
// Find bottleneck
int bottleneck = INT_MAX;
for (int v = t; v != s; ) {
int u = parent[v];
bottleneck = min(bottleneck, graph[u][parentEdge[v]].cap);
v = u;
}
// Update residual capacities
for (int v = t; v != s; ) {
int u = parent[v];
graph[u][parentEdge[v]].cap -= bottleneck;
graph[graph[u][parentEdge[v]].to][graph[u][parentEdge[v]].rev].cap += bottleneck;
v = u;
}
flow += bottleneck;
}
return flow;
}
// Find min-cut after computing max-flow
vector<pair<int,int>> minCut(int s) {
// BFS from s in residual graph
vector<bool> visited(n, false);
queue<int> q;
visited[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v]) {
if (!visited[e.to] && e.cap > 0) {
visited[e.to] = true;
q.push(e.to);
}
}
}
// Edges crossing from visited (S) to unvisited (T) form the min-cut
// Only include forward edges (original capacity > 0) that are fully saturated
vector<pair<int,int>> cut;
for (int u = 0; u < n; u++) {
if (!visited[u]) continue;
for (int i = 0; i < (int)graph[u].size(); i++) {
auto& e = graph[u][i];
if (!visited[e.to] && e.cap == 0) {
// Check this is a forward edge: its reverse has cap > 0
auto& rev = graph[e.to][e.rev];
if (rev.cap > 0) {
cut.push_back({u, e.to});
}
}
}
}
return cut;
}
};
int main() {
EdmondsKarp ek(6);
// s=0, A=1, B=2, C=3, D=4, t=5
ek.addEdge(0, 1, 7);
ek.addEdge(0, 2, 4);
ek.addEdge(1, 2, 3);
ek.addEdge(1, 3, 5);
ek.addEdge(2, 4, 6);
ek.addEdge(3, 5, 8);
ek.addEdge(4, 5, 5);
ek.addEdge(3, 4, 2);
cout << "Max flow: " << ek.maxFlow(0, 5) << endl;
// Output: Max flow: 10
auto cut = ek.minCut(0);
cout << "Min cut edges:" << endl;
for (auto [u, v] : cut) {
cout << " " << u << " -> " << v << endl;
}
}
Complexity:
- Time: O(V * E^2). At most O(VE) augmentations, each BFS takes O(E).
- Space: O(V + E)
Dinic's Algorithm
The Key Innovation: Level Graphs and Blocking Flows
Dinic's algorithm improves on Edmonds-Karp by finding multiple augmenting paths in a single BFS phase. It uses two key concepts:
Level Graph: Assign each vertex a level = BFS distance from s. Only keep edges (u, v) where level[v] = level[u] + 1. This creates a DAG where every path from s to t has the same length.
Blocking Flow: A flow in the level graph such that every s-to-t path has at least one saturated edge. A single blocking flow can incorporate many augmenting paths.
Algorithm Steps
Dinic's Algorithm:
1. BFS from s to build level graph (assign levels).
If t is unreachable, stop -- current flow is maximum.
2. Find a blocking flow in the level graph using DFS.
Use the "current arc" optimization to avoid revisiting dead ends.
3. Add blocking flow to total flow.
4. Go to step 1.
Why O(V^2 * E)?
- Number of phases: At most O(V). Each phase increases the BFS distance from s to t by at least 1, and the maximum distance is V-1.
- Each phase: BFS takes O(E). Finding a blocking flow with the current-arc optimization takes O(VE) -- each DFS path either reaches t (at most E saturations total) or retreats and permanently eliminates a dead-end edge.
- Total: O(V) phases * O(VE) per phase = O(V^2 * E).
For unit capacity graphs, Dinic's runs in O(E * sqrt(V)), which is particularly useful for bipartite matching.
Comparison with Edmonds-Karp
Complete C++ Implementation
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev;
int cap;
};
class Dinic {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
// BFS to build level graph
bool bfs(int s, int t) {
level.assign(n, -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;
}
// DFS to find blocking flow with current-arc optimization
int dfs(int v, int t, int 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]) {
int 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;
}
public:
Dinic(int n) : n(n), graph(n), level(n), iter(n) {}
void addEdge(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) { // Phase: build level graph
iter.assign(n, 0); // Reset current-arc pointers
int d;
while ((d = dfs(s, t, INT_MAX)) > 0) { // Find blocking flow
flow += d;
}
}
return flow;
}
// Find min-cut: vertices reachable from s in residual graph
vector<bool> minCutS(int s) {
vector<bool> inS(n, false);
queue<int> q;
inS[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v]) {
if (e.cap > 0 && !inS[e.to]) {
inS[e.to] = true;
q.push(e.to);
}
}
}
return inS;
}
};
int main() {
Dinic dinic(6);
// s=0, A=1, B=2, C=3, D=4, t=5
dinic.addEdge(0, 1, 10);
dinic.addEdge(0, 2, 10);
dinic.addEdge(1, 3, 6);
dinic.addEdge(1, 2, 4);
dinic.addEdge(2, 4, 10);
dinic.addEdge(3, 5, 8);
dinic.addEdge(3, 4, 3);
dinic.addEdge(4, 5, 7);
cout << "Max flow: " << dinic.maxFlow(0, 5) << endl;
// Output: Max flow: 15
}
Complexity:
- Time: O(V^2 * E) in general. O(E * sqrt(V)) for unit capacity graphs.
- Space: O(V + E)
The current-arc optimization is critical. The iter[v] array remembers which edges from
vertex v have already been explored in the current phase. When DFS backtracks from v, we
don't re-explore edges that already led to dead ends. This is what makes the blocking flow
computation efficient.
Bipartite Matching
Reduction to Max-Flow
A bipartite matching is a set of edges in a bipartite graph such that no vertex appears in more than one edge. The maximum bipartite matching has the most edges possible.
The reduction to max-flow is elegant:
Construction:
- Add source s with edges to every left vertex (capacity 1)
- Add sink t with edges from every right vertex (capacity 1)
- Keep all bipartite edges (capacity 1, directed left to right)
- Run max-flow. The flow value equals the maximum matching size.
Why it works: The capacity-1 edges from s and to t ensure each vertex is matched at most once. Each unit of flow corresponds to one matched edge.
Hopcroft-Karp Algorithm
Hopcroft-Karp is essentially Dinic's algorithm applied to bipartite graphs. It achieves O(E * sqrt(V)) time for bipartite matching.
The idea: instead of finding augmenting paths one at a time, find a maximal set of vertex-disjoint shortest augmenting paths in each phase (exactly what Dinic's blocking flow does).
Complete C++ Implementation (Augmenting Path Matching)
This simpler O(V * E) implementation is often sufficient for interviews:
#include <bits/stdc++.h>
using namespace std;
class BipartiteMatching {
int n, m; // left size, right size
vector<vector<int>> adj; // adjacency list for left vertices
vector<int> matchL, matchR;
bool dfs(int u, vector<bool>& visited) {
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
// If v is unmatched or we can find an alternating path
if (matchR[v] == -1 || dfs(matchR[v], visited)) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
return false;
}
public:
BipartiteMatching(int n, int m) : n(n), m(m), adj(n) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
int maxMatching() {
matchL.assign(n, -1);
matchR.assign(m, -1);
int matching = 0;
for (int u = 0; u < n; u++) {
vector<bool> visited(m, false);
if (dfs(u, visited)) {
matching++;
}
}
return matching;
}
// Returns matching as list of (left, right) pairs
vector<pair<int,int>> getMatching() {
vector<pair<int,int>> result;
for (int u = 0; u < n; u++) {
if (matchL[u] != -1) {
result.push_back({u, matchL[u]});
}
}
return result;
}
};
int main() {
// 3 left vertices, 3 right vertices
BipartiteMatching bm(3, 3);
bm.addEdge(0, 0); // L0 - R0
bm.addEdge(0, 1); // L0 - R1
bm.addEdge(1, 1); // L1 - R1
bm.addEdge(1, 2); // L1 - R2
bm.addEdge(2, 2); // L2 - R2
cout << "Max matching: " << bm.maxMatching() << endl;
// Output: Max matching: 3
for (auto [l, r] : bm.getMatching()) {
cout << " L" << l << " - R" << r << endl;
}
// Output:
// L0 - R0
// L1 - R1
// L2 - R2
}
Complexity:
- Time: O(V * E). Each DFS is O(E), and we run DFS for each left vertex.
- Space: O(V + E)
Hopcroft-Karp C++ Implementation
#include <bits/stdc++.h>
using namespace std;
class HopcroftKarp {
int n, m;
vector<vector<int>> adj;
vector<int> matchL, matchR, dist;
bool bfs() {
queue<int> q;
for (int u = 0; u < n; u++) {
if (matchL[u] == -1) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = INT_MAX;
}
}
bool found = false;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
int w = matchR[v]; // w is the left vertex matched to v
if (w == -1) {
found = true; // found an augmenting path
} else if (dist[w] == INT_MAX) {
dist[w] = dist[u] + 1;
q.push(w);
}
}
}
return found;
}
bool dfs(int u) {
for (int v : adj[u]) {
int w = matchR[v];
if (w == -1 || (dist[w] == dist[u] + 1 && dfs(w))) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
dist[u] = INT_MAX; // mark as dead end
return false;
}
public:
HopcroftKarp(int n, int m) : n(n), m(m), adj(n), dist(n) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
int maxMatching() {
matchL.assign(n, -1);
matchR.assign(m, -1);
int matching = 0;
while (bfs()) {
for (int u = 0; u < n; u++) {
if (matchL[u] == -1) {
if (dfs(u)) matching++;
}
}
}
return matching;
}
};
int main() {
HopcroftKarp hk(4, 4);
hk.addEdge(0, 0);
hk.addEdge(0, 1);
hk.addEdge(1, 0);
hk.addEdge(1, 2);
hk.addEdge(2, 1);
hk.addEdge(2, 3);
hk.addEdge(3, 2);
hk.addEdge(3, 3);
cout << "Max matching: " << hk.maxMatching() << endl;
// Output: Max matching: 4
}
Complexity:
- Time: O(E * sqrt(V)). At most O(sqrt(V)) phases, each taking O(E).
- Space: O(V + E)
Applications and Reductions
1. Minimum Vertex Cover (Konig's Theorem)
Konig's Theorem: In a bipartite graph, the size of the minimum vertex cover equals the size of the maximum matching.
A vertex cover is a set of vertices such that every edge has at least one endpoint in the set.
Konig's Theorem: min vertex cover = max matching (bipartite only!)
To find the actual vertices in the minimum vertex cover:
1. Compute maximum matching.
2. Build residual graph (unmatched L -> matched R, matched R -> matched L).
3. BFS/DFS from all unmatched left vertices.
4. Minimum vertex cover = (unreached left vertices) UNION (reached right vertices).
Note: This does NOT hold for general graphs. For general graphs, minimum vertex cover is NP-hard.
2. Maximum Independent Set
An independent set is a set of vertices with no edges between them.
Key identity (bipartite graphs): Maximum independent set = V - minimum vertex cover = V - max matching.
This is the complement of the vertex cover: a vertex is in the independent set if and only if it is NOT in the vertex cover.
3. Edge-Disjoint Paths
Problem: Find the maximum number of edge-disjoint paths from s to t (no two paths share an edge).
Reduction: This is exactly max-flow with all edge capacities = 1. Each unit of flow corresponds to one edge-disjoint path.
For vertex-disjoint paths (no two paths share a vertex), use vertex splitting: replace each vertex v (except s, t) with two vertices v_in and v_out connected by an edge of capacity 1. Redirect all incoming edges to v_in and all outgoing edges from v_out.
4. Project Selection / Closure Problem
Problem: You have projects with profits (positive) or costs (negative). Some projects require other projects as prerequisites. Choose a subset of projects to maximize total profit.
Reduction to min-cut:
- Create source s and sink t.
- For each profitable project p (profit > 0): add edge s -> p with capacity = profit.
- For each costly project c (cost > 0): add edge c -> t with capacity = cost.
- For each dependency "project a requires project b": add edge a -> b with capacity = infinity.
- Max profit = (sum of all profits) - min cut.
Intuition: Cutting an s-to-project edge means giving up that project's profit. Cutting a project-to-t edge means paying that project's cost. Infinity-capacity dependency edges can never be cut, so if you select a project, you must also select its prerequisites.
Classic Problems with Full Solutions
Problem 1: Maximum Flow in a Network
Problem: Given a directed graph with capacities, find the maximum flow from source to sink.
This is the fundamental problem. Use Dinic's algorithm for best general-purpose performance.
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev, cap;
};
class MaxFlow {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
bool bfs(int s, int t) {
level.assign(n, -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;
}
int dfs(int v, int t, int 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]) {
int 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;
}
public:
MaxFlow(int n) : n(n), graph(n), level(n), iter(n) {}
void addEdge(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
long long solve(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
iter.assign(n, 0);
int d;
while ((d = dfs(s, t, INT_MAX)) > 0)
flow += d;
}
return flow;
}
};
int main() {
int V, E;
cin >> V >> E;
int s, t;
cin >> s >> t;
MaxFlow mf(V);
for (int i = 0; i < E; i++) {
int u, v, c;
cin >> u >> v >> c;
mf.addEdge(u, v, c);
}
cout << mf.solve(s, t) << endl;
}
Complexity: O(V^2 * E) time, O(V + E) space.
Problem 2: Minimum Cut
Problem: Find the minimum set of edges whose removal disconnects s from t, with minimum total capacity.
By the max-flow min-cut theorem, compute the max-flow, then find the min-cut from the residual graph.
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev, cap;
int origCap; // store original capacity for reporting
};
class MinCut {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
bool bfs(int s, int t) {
level.assign(n, -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;
}
int dfs(int v, int t, int 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]) {
int 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;
}
public:
MinCut(int n) : n(n), graph(n), level(n), iter(n) {}
void addEdge(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap, cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0, 0});
}
long long maxFlow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
iter.assign(n, 0);
int d;
while ((d = dfs(s, t, INT_MAX)) > 0)
flow += d;
}
return flow;
}
// Call after maxFlow()
// Returns edges in the min-cut as (from, to, capacity)
vector<tuple<int,int,int>> findMinCut(int s) {
// BFS from s in residual graph to find reachable set S
vector<bool> reachable(n, false);
queue<int> q;
reachable[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v]) {
if (e.cap > 0 && !reachable[e.to]) {
reachable[e.to] = true;
q.push(e.to);
}
}
}
// Edges from S to V-S with original capacity > 0 are cut edges
vector<tuple<int,int,int>> cutEdges;
for (int u = 0; u < n; u++) {
if (!reachable[u]) continue;
for (auto& e : graph[u]) {
if (!reachable[e.to] && e.origCap > 0) {
cutEdges.push_back({u, e.to, e.origCap});
}
}
}
return cutEdges;
}
};
int main() {
MinCut mc(6);
// s=0, t=5
mc.addEdge(0, 1, 3);
mc.addEdge(0, 2, 3);
mc.addEdge(1, 3, 2);
mc.addEdge(1, 2, 2);
mc.addEdge(2, 4, 3);
mc.addEdge(3, 5, 3);
mc.addEdge(4, 5, 2);
mc.addEdge(3, 4, 1);
long long flow = mc.maxFlow(0, 5);
cout << "Max flow (= min cut): " << flow << endl;
auto cut = mc.findMinCut(0);
cout << "Min cut edges:" << endl;
for (auto [u, v, c] : cut) {
cout << " " << u << " -> " << v << " (cap " << c << ")" << endl;
}
}
Complexity: O(V^2 * E) for max-flow + O(V + E) for BFS to find cut.
Problem 3: Maximum Bipartite Matching
Problem: Given a bipartite graph, find the maximum matching.
Classic applications: job assignments, course scheduling, pairing problems.
#include <bits/stdc++.h>
using namespace std;
// Simple augmenting path matching (O(V*E))
class MaxMatching {
int n, m;
vector<vector<int>> adj;
vector<int> matchL, matchR;
bool augment(int u, vector<bool>& vis) {
for (int v : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
if (matchR[v] == -1 || augment(matchR[v], vis)) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
return false;
}
public:
MaxMatching(int n, int m) : n(n), m(m), adj(n) {}
void addEdge(int u, int v) { adj[u].push_back(v); }
int solve() {
matchL.assign(n, -1);
matchR.assign(m, -1);
int result = 0;
for (int u = 0; u < n; u++) {
vector<bool> vis(m, false);
if (augment(u, vis)) result++;
}
return result;
}
vector<pair<int,int>> getMatching() {
vector<pair<int,int>> res;
for (int i = 0; i < n; i++)
if (matchL[i] != -1)
res.push_back({i, matchL[i]});
return res;
}
};
int main() {
// Example: 3 workers, 4 jobs
// Worker 0 can do jobs {0, 1}
// Worker 1 can do jobs {1, 2}
// Worker 2 can do jobs {2, 3}
MaxMatching mm(3, 4);
mm.addEdge(0, 0); mm.addEdge(0, 1);
mm.addEdge(1, 1); mm.addEdge(1, 2);
mm.addEdge(2, 2); mm.addEdge(2, 3);
cout << "Max matching: " << mm.solve() << endl;
// Output: 3
for (auto [w, j] : mm.getMatching())
cout << " Worker " << w << " -> Job " << j << endl;
// One valid output:
// Worker 0 -> Job 0
// Worker 1 -> Job 1
// Worker 2 -> Job 2
}
Complexity: O(V * E) time, O(V + E) space.
Problem 4: Edge-Disjoint Paths
Problem: Find the maximum number of edge-disjoint paths from s to t in a directed graph.
By Menger's theorem, this equals the max-flow with all capacities = 1.
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev, cap;
};
class EdgeDisjointPaths {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
bool bfs(int s, int t) {
level.assign(n, -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;
}
int dfs(int v, int t, int 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]) {
int 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;
}
public:
EdgeDisjointPaths(int n) : n(n), graph(n), level(n), iter(n) {}
// For edge-disjoint: all capacities are 1
void addEdge(int from, int to) {
graph[from].push_back({to, (int)graph[to].size(), 1});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
int solve(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
iter.assign(n, 0);
int d;
while ((d = dfs(s, t, INT_MAX)) > 0)
flow += d;
}
return flow;
}
// Reconstruct the actual paths
vector<vector<int>> findPaths(int s, int t) {
int numPaths = solve(s, t);
// Note: after max-flow, edges with cap=0 were used (originally cap=1)
// Rebuild which edges carry flow
vector<vector<int>> paths;
vector<vector<bool>> used(n);
for (int i = 0; i < n; i++)
used[i].assign(graph[i].size(), false);
// Mark used edges (forward edges with cap=0 were used)
for (int u = 0; u < n; u++) {
for (int j = 0; j < (int)graph[u].size(); j++) {
if (graph[u][j].cap == 0 && j % 2 == 0) {
// Original forward edge that was used
// (even index = forward edge in our construction)
}
}
}
// Simpler: trace paths greedily from s
for (int p = 0; p < numPaths; p++) {
vector<int> path = {s};
vector<vector<bool>> visited(n);
for (int i = 0; i < n; i++)
visited[i].assign(graph[i].size(), false);
int cur = s;
while (cur != t) {
bool found = false;
for (int j = 0; j < (int)graph[cur].size(); j++) {
Edge& e = graph[cur][j];
// Backward edge has residual = 1 (was 0, flow gave it 1)
// So a "used" forward edge has cap=0
// We look for edges where original cap was 1 and current cap is 0
if (!visited[cur][j] && e.cap == 0 &&
graph[e.to][e.rev].cap == 1) {
visited[cur][j] = true;
// "Un-use" this edge so next path doesn't reuse it
e.cap = 1;
graph[e.to][e.rev].cap = 0;
path.push_back(e.to);
cur = e.to;
found = true;
break;
}
}
if (!found) break;
}
if (cur == t) paths.push_back(path);
}
return paths;
}
};
int main() {
// Graph with 6 vertices
EdgeDisjointPaths edp(6);
edp.addEdge(0, 1);
edp.addEdge(0, 2);
edp.addEdge(0, 3);
edp.addEdge(1, 4);
edp.addEdge(2, 4);
edp.addEdge(3, 4);
edp.addEdge(1, 5);
edp.addEdge(4, 5);
edp.addEdge(3, 5);
cout << "Max edge-disjoint paths from 0 to 5: "
<< edp.solve(0, 5) << endl;
// Output: 3
}
Complexity: O(E * sqrt(V)) using Dinic's on unit-capacity graph.
Vertex-disjoint paths: Split each vertex v into v_in and v_out with edge (v_in, v_out) of capacity 1. Redirect incoming edges to v_in and outgoing to v_out. Then solve edge-disjoint.
Problem 5: Project Selection (Closure Problem)
Problem: You have n projects. Each project i has a value w_i (positive = profit, negative = cost). Some projects have prerequisites: project i requires project j to also be selected. Find the subset with maximum total value.
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev, cap;
};
class ProjectSelection {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
bool bfs(int s, int t) {
level.assign(n, -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;
}
int dfs(int v, int t, int 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]) {
int 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;
}
void addEdgeInternal(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
public:
// numProjects = number of projects, s = numProjects, t = numProjects+1
ProjectSelection(int numProjects) : n(numProjects + 2),
graph(numProjects + 2), level(numProjects + 2), iter(numProjects + 2) {}
int source() { return n - 2; }
int sink() { return n - 1; }
// Call this for each project
// If value > 0: profitable project, add edge s -> project with cap = value
// If value < 0: costly project, add edge project -> t with cap = -value
void setProjectValue(int project, int value) {
if (value > 0) {
addEdgeInternal(source(), project, value);
} else if (value < 0) {
addEdgeInternal(project, sink(), -value);
}
}
// Project 'from' requires project 'to'
// Add edge from -> to with cap = infinity
void addDependency(int from, int to) {
addEdgeInternal(from, to, INT_MAX / 2);
}
// Returns maximum profit and which projects to select
pair<long long, vector<int>> solve(vector<int>& values) {
long long sumPositive = 0;
for (int i = 0; i < (int)values.size(); i++) {
setProjectValue(i, values[i]);
if (values[i] > 0) sumPositive += values[i];
}
// Compute min-cut
long long flow = 0;
int s = source(), t = sink();
while (bfs(s, t)) {
iter.assign(n, 0);
int d;
while ((d = dfs(s, t, INT_MAX)) > 0)
flow += d;
}
// Selected projects = those reachable from s in residual graph
vector<bool> reachable(n, false);
queue<int> q;
reachable[s] = true;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : graph[v]) {
if (e.cap > 0 && !reachable[e.to]) {
reachable[e.to] = true;
q.push(e.to);
}
}
}
vector<int> selected;
for (int i = 0; i < (int)values.size(); i++) {
if (reachable[i]) selected.push_back(i);
}
return {sumPositive - flow, selected};
}
};
int main() {
// 5 projects with values: [10, 8, -5, -3, 6]
// Dependencies: project 0 requires project 2,
// project 1 requires project 3,
// project 4 requires project 2
vector<int> values = {10, 8, -5, -3, 6};
ProjectSelection ps(5);
// Set dependencies before solve
ps.addDependency(0, 2); // project 0 needs project 2
ps.addDependency(1, 3); // project 1 needs project 3
ps.addDependency(4, 2); // project 4 needs project 2
auto [profit, selected] = ps.solve(values);
cout << "Max profit: " << profit << endl;
cout << "Selected projects:";
for (int p : selected) cout << " " << p;
cout << endl;
// Selects projects 0, 1, 2, 3, 4 with profit = 10+8-5-3+6 = 16
// Or a subset depending on the actual min-cut
}
Complexity: O(V^2 * E) for Dinic's max-flow.
Problem 6: Escape from a Grid (Vertex Capacities)
Problem: Given a grid where some cells are blocked, find the maximum number of vertex-disjoint paths from source cells to the boundary. Each cell can only be used by one path.
This demonstrates the vertex splitting technique.
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, rev, cap;
};
class GridEscape {
int n;
vector<vector<Edge>> graph;
vector<int> level, iter;
bool bfs(int s, int t) {
level.assign(n, -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;
}
int dfs(int v, int t, int 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]) {
int 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;
}
void addEdge(int from, int to, int cap) {
graph[from].push_back({to, (int)graph[to].size(), cap});
graph[to].push_back({from, (int)graph[from].size() - 1, 0});
}
public:
// Vertex splitting: cell (r,c) becomes two nodes:
// in-node = 2*(r*cols + c)
// out-node = 2*(r*cols + c) + 1
// Connected by edge of capacity 1 (vertex capacity)
int solve(vector<vector<int>>& grid, vector<pair<int,int>>& sources) {
int rows = grid.size(), cols = grid[0].size();
int totalCells = rows * cols;
// Nodes: 2*totalCells for split + 1 source + 1 sink
n = 2 * totalCells + 2;
int S = n - 2, T = n - 1;
graph.assign(n, {});
level.resize(n);
iter.resize(n);
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) continue; // blocked
int id = r * cols + c;
int inNode = 2 * id;
int outNode = 2 * id + 1;
// Internal edge: in -> out, capacity 1 (vertex cap)
addEdge(inNode, outNode, 1);
// Connect to neighbors
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& grid[nr][nc] == 0) {
int nid = nr * cols + nc;
addEdge(outNode, 2 * nid, 1); // out -> neighbor's in
}
}
// Boundary cells connect to sink
if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
addEdge(outNode, T, 1);
}
}
}
// Source connects to all source cells
for (auto [r, c] : sources) {
int id = r * cols + c;
addEdge(S, 2 * id, 1);
}
// Run Dinic's
int flow = 0;
while (bfs(S, T)) {
iter.assign(n, 0);
int d;
while ((d = dfs(S, T, INT_MAX)) > 0)
flow += d;
}
return flow;
}
};
int main() {
// 0 = open, 1 = blocked
vector<vector<int>> grid = {
{0, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 1, 0},
{0, 0, 0, 0}
};
vector<pair<int,int>> sources = {{1, 0}, {2, 1}};
GridEscape ge;
cout << "Max escaping paths: " << ge.solve(grid, sources) << endl;
// Output: 2
}
Complexity: O(V^2 * E) where V and E are the vertices and edges of the flow graph (which is O(RC) vertices and O(RC) edges for an R x C grid).
Common Mistakes and Interview Tips
1. Forgetting Backward Edges
The single most common implementation bug. Every forward edge (u, v) with capacity c needs a corresponding backward edge (v, u) with capacity 0. The backward edge enables flow rerouting.
Wrong:
// Only adding forward edge
graph[u].push_back({v, cap});
Right:
// Add forward and backward edges, linked via rev pointers
graph[u].push_back({v, (int)graph[v].size(), cap});
graph[v].push_back({u, (int)graph[u].size() - 1, 0});
2. Confusing Undirected and Directed Edges
For an undirected edge with capacity c, you need to add it as two directed edges, each with capacity c. But each still needs its reverse edge:
// Undirected edge (u, v) with capacity c:
// Add u->v with cap c, and v->u with cap c
// Both share the same reverse pair
void addUndirectedEdge(int u, int v, int cap) {
graph[u].push_back({v, (int)graph[v].size(), cap});
graph[v].push_back({u, (int)graph[u].size() - 1, cap}); // cap, not 0!
}
A common mistake is using 0 for the reverse capacity (which would make it directed).
3. Integer Overflow with Large Capacities
When capacities are up to 10^9 and the graph has many edges, the total flow can exceed
int range. Use long long for the flow accumulator.
// Wrong
int totalFlow = 0; // overflows if flow > 2*10^9
// Right
long long totalFlow = 0;
Also, when using INT_MAX as infinity for dependencies, be careful:
// Wrong: INT_MAX + INT_MAX overflows
int cap = INT_MAX;
// Right: use a safe large value
int INF = 1e9; // or INT_MAX / 2
4. Not Resetting State Between Phases (Dinic's)
The iter array (current-arc pointers) must be reset at the start of each phase, not each
DFS call. This is the current-arc optimization -- without it, Dinic's degrades to O(V * E^2).
while (bfs(s, t)) {
iter.assign(n, 0); // Reset HERE, once per phase
int d;
while ((d = dfs(s, t, INT_MAX)) > 0) {
// Do NOT reset iter here
flow += d;
}
}
5. Wrong Min-Cut Extraction
After computing max-flow, the min-cut is found by BFS/DFS in the residual graph (using edges with remaining capacity > 0), not the original graph.
// Wrong: checking if original edge is saturated
if (originalCap[u][v] == flow[u][v]) // not reliable
// Right: BFS in residual graph from source
// S = reachable from s using edges with residual capacity > 0
// Cut edges: (u,v) where u in S, v not in S, and (u,v) is an original edge
6. Incorrect Bipartite Matching Setup
When reducing bipartite matching to max-flow, the edges must go in one direction (left to right). Adding edges in both directions creates a different (and wrong) problem.
Also, the capacity of every edge must be exactly 1. Using larger capacities would allow a vertex to be matched multiple times.
7. Forgetting Vertex Splitting for Vertex Capacities
If the problem has a vertex capacity constraint (each vertex can be used at most k times), you must split the vertex. Just reducing the capacity of adjacent edges does NOT correctly enforce vertex capacity.
// To enforce vertex v can be used at most k times:
// Split v into v_in and v_out
// Add edge v_in -> v_out with capacity k
// Redirect incoming edges to v_in, outgoing from v_out
Interview Tips
-
Start with the reduction: In interviews, the hardest part is usually recognizing that a problem reduces to network flow. Practice identifying the source, sink, and what capacity means.
-
Know which algorithm to use:
- Small graphs, simple problems: Edmonds-Karp
- General competitive programming: Dinic's
- Bipartite matching: Hungarian or Hopcroft-Karp (or Dinic's)
-
Explain the max-flow min-cut theorem: Interviewers love asking why the min-cut equals the max-flow. Have the three-part proof intuition ready.
-
Common patterns to recognize:
- "Minimum number of X to disconnect Y" = min-cut
- "Maximum number of non-overlapping paths" = max-flow with unit capacities
- "Assign items to slots with constraints" = bipartite matching
- "Select a subset with dependencies to maximize profit" = project selection
-
Draw the flow network: Always draw the reduction before coding. Label source, sink, capacities, and verify the constraints are correctly modeled.