Edmonds-Karp.cpp

/*
    Author : M. A. Rafsan Mazumder
    Algorithm : Edmonds-Karp Algorithm for Maximum Flow
    Complexity : V*E^2
    Problem : LightOJ - 1153
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 105
vector<int> adj[MAX];
bool vis[MAX];
int parent[MAX];
int rGraph[MAX][MAX];
int S, T;

void addedge(int u, int v, int cap)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
    rGraph[u][v] += cap;
    rGraph[v][u] += cap; // As Bidirectional, if unidirectional rGraph[v][u] = 0
}


void reset()
{
    for(int i=0; i<MAX; i++){
        adj[i].clear();
        for(int j=0; j<MAX; j++) rGraph[i][j] = 0;
        parent[i] = -1;
    }
}

bool bfs()
{
    memset(vis, false, sizeof vis);
    queue<int> Q;
    Q.push(S);
    vis[S] = true;

    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i=0; i<adj[u].size(); i++){
            int v = adj[u][i];
            if(vis[v] == false && rGraph[u][v] > 0){
                vis[v] = true;
                parent[v] = u;
                Q.push(v);
            }
        }
    }
    return (vis[T] == true);
}

int edmonds_karp()
{
    int max_flow = 0;
    while(bfs()){
        int path_flow = INT_MAX;
        int u, v;
        for(v=T; v!=S; v=parent[v]){
            u = parent[v];
            path_flow = min(path_flow, rGraph[u][v]);
        }
        for(v=T; v!=S; v=parent[v]){
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int main()
{
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        reset();
        int node, edge;
        scanf("%d", &node);
        scanf("%d %d %d", &S, &T, &edge);
        for(int i=0; i<edge; i++){
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            addedge(u, v, c);
        }
        printf("Case %d: %d\n", ++caseno, edmonds_karp());
    }
}

/*
    4
    4
    1 4 2
    4 1 232
    1 4 490
    3
    1 2 2
    3 2 188
    2 1 100
    7
    2 6 6
    3 6 127
    3 4 515
    4 6 114
    2 3 123
    7 1 866
    4 7 588
    3
    3 1 7
    1 3 763
    1 2 883
    3 1 383
    1 2 641
    2 1 411
    2 3 229
    2 1 345

    Case 1: 722
    Case 2: 100
    Case 3: 123
    Case 4: 1375
*/