Hey everyone! <br>↵
↵
We were taught basic network flow in our algorithms course in university and I started to learn it. Found this useful blog↵
blog by [user:Zhtluo,2025-10-21] [link](https://mirror.codeforces.com/blog/entry/141680)↵
↵
### Target Audience.↵
This post is for anyone who has some free time :)<br>↵
↵
<spoiler summary="Help if you can spare some time">↵
To do the first kind of problems Graph Matching. I went through William Fiset’s amazing YouTube playlist on Network Flow↵
Since I learned it all from one source, I wanted to write this blog to share what I understood — and more importantly — to ask the community for new perspectives and interesting problems to explore using this algorithm. <br>↵
</spoiler>↵
↵
### Basic↵
↵
<spoiler summary="What is network flow">↵
Imagine you have a water system:<br><br>↵
A big tank (source) that sends water to↵
A fountain (sink) through↵
Several pipes (edges) connected by junctions (nodes). <br><br>↵
Each pipe has a limit — called capacity — which represents how much water it can carry. <br><br>↵
 <br>↵
Our goal?↵
➡️ Find the maximum amount of water that can flow from the tank (source) to the fountain (sink). <br><br>↵
</spoiler>↵
↵
### Bipartite Matching Example↵
Suppose we have two sets: <br>↵
Set A = people↵
Set B = books <br><br>↵
↵
Each person likes certain books, and we want to find the maximum number of unique person-book matches, where each person gets exactly one book they like. <br><br>↵
Here’s how Network Flow helps:↵
Connect the source to all people.↵
Connect each person to the books they like.↵
Connect all books to the sink. <br><br>↵
↵
Then, when we run a maximum flow algorithm, the maximum flow value will tell us the number of unique person-book pairs that can be matched. <br>↵
This is basically the maximum bipartite matching problem. <br><br>↵
↵
The Ford–Fulkerson Algorithm↵
------------------↵
We keep finding paths from the source to the sink that still have some remaining capacity, and push as much flow as possible through them — until no such paths exist. <br><br>↵
### Steps↵
1. Use DFS to find a path from source to sink.↵
↵
2. Find the smallest capacity (bottleneck) along that path.↵
↵
3. Send that much “water” (flow) through the path.↵
↵
4. Add a reverse edge to allow undoing flow later.↵
↵
5. Repeat until no more augmenting paths exist. <br><br>↵
↵
### Time Complexity↵
O(E × f) where f is the value of the maximum flow. <br><br>↵
↵
### Code↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
typedef struct{↵
int to;↵
int flow;↵
int capacity;↵
int rev; // index of reverse edge↵
}edge;↵
↵
int source;↵
int sink;↵
vector<vector<edge>> adj;↵
↵
void addedge(int from, int to, int cap){↵
adj[from].push_back({to, 0, cap, (int)adj[to].size()});↵
adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1}); // reverse edge↵
}↵
↵
int dfs(int curr, vector<bool> & visited, int bottleneck){↵
if(curr == sink){↵
return bottleneck;↵
}↵
visited[curr] = true;↵
↵
for (int i = 0; i < adj[curr].size(); i++){↵
edge &e = adj[curr][i];↵
if(!visited[e.to] && e.capacity - e.flow > 0){↵
int flow = dfs(e.to, visited, min(bottleneck, e.capacity - e.flow));↵
if(flow > 0){↵
e.flow += flow;↵
adj[e.to][e.rev].flow -= flow; // update reverse edge↵
return flow;↵
}↵
}↵
}↵
return 0;↵
}↵
↵
int fordFulkerson(){↵
int maxflow = 0;↵
while(true){↵
vector<bool> visited(adj.size(), false);↵
int flow = dfs(source, visited, INT_MAX);↵
if(flow == 0) break;↵
maxflow += flow;↵
}↵
return maxflow;↵
}↵
~~~~~↵
...↵
</spoiler>↵
↵
It’s conceptually simple but can be slow if the capacities are large because runtime depends directly on the flow value. <br><br>↵
↵
The Edmonds–Karp Algorithm↵
------------------↵
This is an optimized version of Ford–Fulkerson that uses BFS instead of DFS to find augmenting paths. <br><br>↵
Why BFS?↵
Using DFS can lead to zig-zagging paths that push very little flow each time, making the algorithm slow.↵
BFS ensures we always find the shortest path (in terms of number of edges), which makes the process much more efficient. <br><br>↵
### Steps↵
1. Use BFS to find the shortest augmenting path.↵
↵
2. Find the bottleneck capacity on that path.↵
↵
3. Push flow along the path and update reverse edges.↵
↵
4. Repeat until no more augmenting paths exist. <br><br>↵
↵
### Time Complexity↵
O(V × E²) <br><br>↵
This guarantees a polynomial runtime↵
↵
### Code↵
↵
<spoiler summary="Code">↵
~~~~~↵
typedef struct{↵
int to;↵
int flow;↵
int capacity;↵
int rev; // index of reverse edge↵
}edge;↵
int source;↵
int sink;↵
vector<vector<edge>> adj;↵
void addedge(int from, int to, int cap){↵
adj[from].push_back({to, 0, cap, (int)adj[to].size()});↵
adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1}); // reverse edge↵
}↵
int bfs(vector<int> &parent){↵
vector<bool> visited(adj.size(), false);↵
queue<int> q;↵
q.push(source);↵
visited[source] = true;↵
parent[source] = -1;↵
↵
while(!q.empty()){↵
int curr = q.front();↵
q.pop();↵
↵
for (int i = 0; i < adj[curr].size(); i++){↵
edge &e = adj[curr][i];↵
if(!visited[e.to] && e.capacity - e.flow > 0){↵
q.push(e.to);↵
parent[e.to] = curr;↵
visited[e.to] = true;↵
if(e.to == sink) return 1;↵
}↵
}↵
}↵
return 0;↵
}↵
int edmondsKarp(){↵
int maxflow = 0;↵
vector<int> parent(adj.size());↵
↵
while(bfs(parent)){↵
int flow = INT_MAX;↵
for(int v = sink; v != source; v = parent[v]){↵
int u = parent[v];↵
flow = min(flow, adj[u][v].capacity - adj[u][v].flow);↵
}↵
for(int v = sink; v != source; v = parent[v]){↵
int u = parent[v];↵
adj[u][v].flow += flow;↵
adj[v][adj[u][v].rev].flow -= flow; // update reverse edge↵
}↵
↵
maxflow += flow;↵
}↵
return maxflow;↵
}↵
~~~~~↵
...↵
</spoiler>↵
↵
### PRACTICE PROBLEMS↵
1. [Katis Elementary math](https://open.kattis.com/problems/elementarymath)↵
2. [Katis Gopher2](https://open.kattis.com/problems/gopher2)↵
3. [CF Delivery Bears](https://mirror.codeforces.com/contest/653/problem/D)↵
4. [ICPC regionals I. Magic Potions](https://mirror.codeforces.com/gym/101981/attachments)↵
↵
↵
Again, if possible, please provide new perspectives and interesting problems to explore using this algorithm
↵
We were taught basic network flow in our algorithms course in university and I started to learn it. Found this useful blog↵
blog by [user:Zhtluo,2025-10-21] [link](https://mirror.codeforces.com/blog/entry/141680)↵
↵
### Target Audience.↵
This post is for anyone who has some free time :)<br>↵
↵
<spoiler summary="Help if you can spare some time">↵
To do the first kind of problems Graph Matching. I went through William Fiset’s amazing YouTube playlist on Network Flow↵
Since I learned it all from one source, I wanted to write this blog to share what I understood — and more importantly — to ask the community for new perspectives and interesting problems to explore using this algorithm. <br>↵
</spoiler>↵
↵
### Basic↵
↵
<spoiler summary="What is network flow">↵
Imagine you have a water system:<br><br>↵
A big tank (source) that sends water to↵
A fountain (sink) through↵
Several pipes (edges) connected by junctions (nodes). <br><br>↵
Each pipe has a limit — called capacity — which represents how much water it can carry. <br><br>↵
 <br>↵
Our goal?↵
➡️ Find the maximum amount of water that can flow from the tank (source) to the fountain (sink). <br><br>↵
</spoiler>↵
↵
### Bipartite Matching Example↵
Suppose we have two sets: <br>↵
Set A = people↵
Set B = books <br><br>↵
↵
Each person likes certain books, and we want to find the maximum number of unique person-book matches, where each person gets exactly one book they like. <br><br>↵
Here’s how Network Flow helps:↵
Connect the source to all people.↵
Connect each person to the books they like.↵
Connect all books to the sink. <br><br>↵
↵
Then, when we run a maximum flow algorithm, the maximum flow value will tell us the number of unique person-book pairs that can be matched. <br>↵
This is basically the maximum bipartite matching problem. <br><br>↵
↵
The Ford–Fulkerson Algorithm↵
------------------↵
We keep finding paths from the source to the sink that still have some remaining capacity, and push as much flow as possible through them — until no such paths exist. <br><br>↵
### Steps↵
1. Use DFS to find a path from source to sink.↵
↵
2. Find the smallest capacity (bottleneck) along that path.↵
↵
3. Send that much “water” (flow) through the path.↵
↵
4. Add a reverse edge to allow undoing flow later.↵
↵
5. Repeat until no more augmenting paths exist. <br><br>↵
↵
### Time Complexity↵
O(E × f) where f is the value of the maximum flow. <br><br>↵
↵
### Code↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
typedef struct{↵
int to;↵
int flow;↵
int capacity;↵
int rev; // index of reverse edge↵
}edge;↵
↵
int source;↵
int sink;↵
vector<vector<edge>> adj;↵
↵
void addedge(int from, int to, int cap){↵
adj[from].push_back({to, 0, cap, (int)adj[to].size()});↵
adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1}); // reverse edge↵
}↵
↵
int dfs(int curr, vector<bool> & visited, int bottleneck){↵
if(curr == sink){↵
return bottleneck;↵
}↵
visited[curr] = true;↵
↵
for (int i = 0; i < adj[curr].size(); i++){↵
edge &e = adj[curr][i];↵
if(!visited[e.to] && e.capacity - e.flow > 0){↵
int flow = dfs(e.to, visited, min(bottleneck, e.capacity - e.flow));↵
if(flow > 0){↵
e.flow += flow;↵
adj[e.to][e.rev].flow -= flow; // update reverse edge↵
return flow;↵
}↵
}↵
}↵
return 0;↵
}↵
↵
int fordFulkerson(){↵
int maxflow = 0;↵
while(true){↵
vector<bool> visited(adj.size(), false);↵
int flow = dfs(source, visited, INT_MAX);↵
if(flow == 0) break;↵
maxflow += flow;↵
}↵
return maxflow;↵
}↵
~~~~~↵
...↵
</spoiler>↵
↵
It’s conceptually simple but can be slow if the capacities are large because runtime depends directly on the flow value. <br><br>↵
↵
The Edmonds–Karp Algorithm↵
------------------↵
This is an optimized version of Ford–Fulkerson that uses BFS instead of DFS to find augmenting paths. <br><br>↵
Why BFS?↵
Using DFS can lead to zig-zagging paths that push very little flow each time, making the algorithm slow.↵
BFS ensures we always find the shortest path (in terms of number of edges), which makes the process much more efficient. <br><br>↵
### Steps↵
1. Use BFS to find the shortest augmenting path.↵
↵
2. Find the bottleneck capacity on that path.↵
↵
3. Push flow along the path and update reverse edges.↵
↵
4. Repeat until no more augmenting paths exist. <br><br>↵
↵
### Time Complexity↵
O(V × E²) <br><br>↵
This guarantees a polynomial runtime↵
↵
### Code↵
↵
<spoiler summary="Code">↵
~~~~~↵
typedef struct{↵
int to;↵
int flow;↵
int capacity;↵
int rev; // index of reverse edge↵
}edge;↵
int source;↵
int sink;↵
vector<vector<edge>> adj;↵
void addedge(int from, int to, int cap){↵
adj[from].push_back({to, 0, cap, (int)adj[to].size()});↵
adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1}); // reverse edge↵
}↵
int bfs(vector<int> &parent){↵
vector<bool> visited(adj.size(), false);↵
queue<int> q;↵
q.push(source);↵
visited[source] = true;↵
parent[source] = -1;↵
↵
while(!q.empty()){↵
int curr = q.front();↵
q.pop();↵
↵
for (int i = 0; i < adj[curr].size(); i++){↵
edge &e = adj[curr][i];↵
if(!visited[e.to] && e.capacity - e.flow > 0){↵
q.push(e.to);↵
parent[e.to] = curr;↵
visited[e.to] = true;↵
if(e.to == sink) return 1;↵
}↵
}↵
}↵
return 0;↵
}↵
int edmondsKarp(){↵
int maxflow = 0;↵
vector<int> parent(adj.size());↵
↵
while(bfs(parent)){↵
int flow = INT_MAX;↵
for(int v = sink; v != source; v = parent[v]){↵
int u = parent[v];↵
flow = min(flow, adj[u][v].capacity - adj[u][v].flow);↵
}↵
for(int v = sink; v != source; v = parent[v]){↵
int u = parent[v];↵
adj[u][v].flow += flow;↵
adj[v][adj[u][v].rev].flow -= flow; // update reverse edge↵
}↵
↵
maxflow += flow;↵
}↵
return maxflow;↵
}↵
~~~~~↵
...↵
</spoiler>↵
↵
### PRACTICE PROBLEMS↵
1. [Katis Elementary math](https://open.kattis.com/problems/elementarymath)↵
2. [Katis Gopher2](https://open.kattis.com/problems/gopher2)↵
3. [CF Delivery Bears](https://mirror.codeforces.com/contest/653/problem/D)↵
4. [ICPC regionals I. Magic Potions](https://mirror.codeforces.com/gym/101981/attachments)↵
↵
↵
Again, if possible, please provide new perspectives and interesting problems to explore using this algorithm
