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


Input:
4 5\n0 1 100\n0 2 100\n1 2 1\n1 3 100\n2 3 100\n0 3

Output:
200

Solution in C++


#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 1000;

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

vector<Edge> 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<int> &parent, vector<int> &parentEdge){
    vector<bool> visited(MAX, false);
    queue<int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i=0; i<adj[u].size(); i++){
            Edge &e = adj[u][i];
            if(!visited[e.v] && e.capacity - e.flow > 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<m;i++){
        int u, v, cap;
        cin >> u >> v >> cap;
        addEdge(u, v, cap);
    }
    int s, t;
    cin >> s >> t;
    int maxFlow = 0;
    vector<int> 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;
}