Problem 4: Maximum Flow (Edmonds-Karp)

Problem Statement: Given a flow network, compute the maximum flow from source to sink using the Edmonds-Karp algorithm.

Input

First line contains n and m, number of vertices and edges. Following m lines contain three integers u, v, capacity. Last line contains source and sink vertices.

Output

Print the maximum possible flow from source to sink.

Examples

Solution Explanation

Method 1: Use the Edmonds-Karp algorithm, which is a BFS-based implementation of the Ford-Fulkerson method to find augmenting paths repeatedly. Method 2: Alternatively, one can implement the Dinic's algorithm for maximum flow, which typically runs faster on many networks but is more complex to implement.

Solution in C++


#include 
#include 
#include 
#include 
using namespace std;

const int MAX = 1000;

struct Edge{
    int v, capacity, flow, rev;
};

vector adj[MAX];

void addEdge(int u, int v, int cap){
    Edge a{v, cap, 0, (int)adj[v].size()};
    Edge b{u, 0, 0, (int)adj[u].size()};
    adj[u].push_back(a);
    adj[v].push_back(b);
}

bool bfs(int s, int t, vector &parent, vector &parentEdge){
    vector visited(MAX, false);
    queue q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i=0; i 0){
                q.push(e.v);
                parent[e.v] = u;
                parentEdge[e.v] = i;
                visited[e.v] = true;
                if(e.v == t) return true;
            }
        }
    }
    return false;
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i=0;i> u >> v >> cap;
        addEdge(u, v, cap);
    }
    int s, t;
    cin >> s >> t;
    int maxFlow = 0;
    vector parent(MAX), parentEdge(MAX);
    while(bfs(s, t, parent, parentEdge)){
        int path_flow = 1e9;
        for(int v = t; v != s; v = parent[v]){
            int u = parent[v];
            path_flow = min(path_flow, adj[u][parentEdge[v]].capacity - adj[u][parentEdge[v]].flow);
        }
        for(int v = t; v != s; v = parent[v]){
            int u = parent[v];
            adj[u][parentEdge[v]].flow += path_flow;
            int rev = adj[u][parentEdge[v]].rev;
            adj[v][rev].flow -= path_flow;
        }
        maxFlow += path_flow;
    }
    cout << maxFlow;
    return 0;
}