Maximum flow

Send as much as possible from source to sink without exceeding edge capacities. Edmonds–Karp repeatedly finds residual augmenting paths with BFS.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

Store remaining forward capacity and a reverse edge that can undo flow.
BFS finds a source-to-sink path with positive residual capacity.
Augment by the smallest remaining capacity on that path.
When no residual path remains, a minimum cut certifies maximum flow.
cap is the residual-capacity matrix, not a record of original capacities. BFS chooses a shortest residual path; reducing forward capacities and increasing reverse capacities allows later augmentations to reroute earlier flow.

C++17 implementation

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
// Capacity matrix; merge parallel directed edges by adding capacity.
long long maxflow(vector<vector<long long>>cap,int s,int t){
    if(s==t){
        return 0;
    }
    int n=(int)cap.size()-1;
    long long flow=0;
    while(true){
        vector<int>p(n+1,-1);
        p[s]=s;
        queue<int>q;
        q.push(s);
        while(!q.empty()&&p[t]==-1){
            int v=q.front();
            q.pop();
            for(int u=1;u<=n;++u){
                if(p[u]==-1&&cap[v][u]>0){
                    p[u]=v;
                    q.push(u);
                }
            }
        }
        if(p[t]==-1){
            break;
        }
        long long add=(1LL<<62);
        for(int v=t;v!=s;v=p[v]){
            add=min(add,cap[p[v]][v]);
        }
        for(int v=t;v!=s;v=p[v]){
            cap[p[v]][v]-=add;
            cap[v][p[v]]+=add;
        }
        flow+=add;
    }
    return flow;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source,sink;
    cin>>n>>m>>source>>sink;
    vector<vector<long long>>capacity(n+1,vector<long long>(n+1));
    for(int i=0;i<m;i++){
        int from,to;
        long long amount;
        cin>>from>>to>>amount;
        capacity[from][to]+=amount;
    }
    cout<<maxflow(capacity,source,sink)<<'\n';
}

Complexity analysis

This matrix version: O(V³E) worst-case time, O(V²) space. Adjacency-list Edmonds–Karp gives O(VE²).

Common mistakes and edge cases. Reverse residual edges are essential: later augmentations may need to undo earlier choices.

Example input and output

Read n m source sink and m directed edges from to capacity. Require 2≤n≤100, m≤10000, distinct source/sink, and capacities in 0..10^9. Print the maximum flow value. Parallel capacities are added.

Input

Output

The source can send at most 3+2=5 units. Paths through vertices 2 and 3 deliver all five units to 4.

Practical applications

Use maximum flow for capacity-limited routing, bipartite matching reductions, and minimum-cut models.

Check your understanding

Why add reverse residual capacity?

Put it into practice

Maximize throughput through a small directed pipe network.

Show a hint

Use integer capacities and accumulate parallel edges into the capacity matrix.

← Previous