Ford Fulkerson Max Flow.cpp

/* Ford Fulkerson - Maximum FLow */
/* Author : M. A. Rafsan Mazumder */

#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 max_flow = 0;
int s, t, n, m;

void gen()
{
    for(int i=0; i<MAX; i++) adj[i].clear();
    memset(vis, false, sizeof vis);
    memset(parent, -1, sizeof parent);
    max_flow = 0;
    memset(rGraph, 0, sizeof rGraph);
}

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] && rGraph[u][v] > 0){
                vis[v] = true;
                parent[v] = u;
                Q.push(v);
            }
        }
    }
    return (vis[t] == true);
}

void ford_fulkerson()
{
    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;
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        gen();
        scanf("%d", &n);
        scanf("%d %d %d", &s, &t, &m);
        for(int i=1; i<=m; i++){
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            adj[u].push_back(v);
            adj[v].push_back(u);
            rGraph[u][v] += c;
            rGraph[v][u] += c;
        }
        ford_fulkerson();
        printf("Case %d: %d\n", ++caseno, max_flow);
    }
}