Blog entries - Codeforces

Hey everyone!

We were taught basic network flow in our algorithms course in university and I started to learn it. Found this useful blog blog by Zhtluo link

Target Audience.

This post is for anyone who has some free time :)

Help if you can spare some time

Basic

What is network flow

Bipartite Matching Example

Suppose we have two sets:
Set A = people Set B = books

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.

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.

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.
This is basically the maximum bipartite matching problem.

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.

Steps

Use DFS to find a path from source to sink.
Find the smallest capacity (bottleneck) along that path.
Send that much “water” (flow) through the path.
Add a reverse edge to allow undoing flow later.
Repeat until no more augmenting paths exist.

Time Complexity

O(E × f) where f is the value of the maximum flow.

Code

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;
}

...

It’s conceptually simple but can be slow if the capacities are large because runtime depends directly on the flow value.

The Edmonds–Karp Algorithm

This is an optimized version of Ford–Fulkerson that uses BFS instead of DFS to find augmenting paths.

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.

Steps

Use BFS to find the shortest augmenting path.
Find the bottleneck capacity on that path.
Push flow along the path and update reverse edges.
Repeat until no more augmenting paths exist.

Time Complexity

O(V × E²)

This guarantees a polynomial runtime

Code

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;
}

...