Problem 47: Maximum Flow - Edmonds Karp
Problem Statement: Given a directed graph representing a flow network with n nodes and m edges, where each edge has a capacity, compute the maximum flow from source to sink using the Edmonds-Karp algorithm.
Input
The first line contains four integers n, m, s, and t (source and sink). Each of the next m lines contains three integers u, v, and c representing an edge from u to v with capacity c.
Output
Print the maximum flow from s to t.
Examples
Input:
4 5 1 4
1 2 3
1 3 2
2 3 1
2 4 2
3 4 4
Output:
5
Solution Explanation
Method 1: Implement the Edmonds-Karp algorithm by repeatedly finding the shortest augmenting path via BFS and updating flows along this path until no augmenting path exists. Method 2: Use Dinic's algorithm which builds level graphs and finds blocking flows, but it is more complex though often faster.
Solution in C++
#include
#include
#include
#include
#include
using namespace std;
struct Edge {
int u, v, cap, flow;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
vector edges;
vector> adj(n+1);
auto addEdge = [&](int u, int v, int cap){
Edge e = {u, v, cap, 0};
Edge red = {v, u, 0, 0};
adj[u].push_back(edges.size());
edges.push_back(e);
adj[v].push_back(edges.size());
edges.push_back(red);
};
for (int i=0;i> u >> v >> cap;
addEdge(u, v, cap);
}
int maxFlow = 0;
while(true){
vector parent(n+1, -1);
vector edgeIndex(n+1, -1);
queue q;
q.push(s);
parent[s] = s;
while(!q.empty() && parent[t]==-1){
int u = q.front(); q.pop();
for (int idx : adj[u]){
Edge &e = edges[idx];
if(parent[e.v]==-1 && e.cap - e.flow > 0){
parent[e.v] = u;
edgeIndex[e.v] = idx;
q.push(e.v);
}
}
}
if(parent[t]==-1) break;
int pushFlow = INT_MAX;
for (int v = t; v != s; v = parent[v]){
int idx = edgeIndex[v];
pushFlow = min(pushFlow, edges[idx].cap - edges[idx].flow);
}
for (int v = t; v != s; v = parent[v]){
int idx = edgeIndex[v];
edges[idx].flow += pushFlow;
edges[idx^1].flow -= pushFlow;
}
maxFlow += pushFlow;
}
cout << maxFlow << "
";
return 0;
}