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