FLOW2

flow.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

const int MAXN = 105;
vector <int> g [MAXN];
int c [MAXN][MAXN];
int f [MAXN][MAXN];
int prev [MAXN];
int nodes;

void connect (int i, int j, int cap){
    g[i].push_back(j);
    g[j].push_back(i);
    c[i][j] += cap;
    c[j][i] += cap;
}

bool path (int s, int t){
    for (int i = 0; i <= nodes; i++)
        prev[i] = -1;
    
    queue <int> q;
    q.push(s);
    prev[s] = 0; //Node zero doesn't exist
    
    while (q.size() > 0){
        int u = q.front(); q.pop();
        if (u == t) return true;
        for (int i = 0; i < g[u].size(); i++){
            int v = g[u][i];
            if (prev[v] == -1 and c[u][v] - f[u][v] > 0){
                q.push(v);
                prev[v] = u;
            }
        }
    }
    assert(prev[t] == -1);
    return false;
}

int bottleneck(int s, int t){
    int best = 1 << 30;
    int curr = t;
    while (prev[curr] != 0){
        //printf("Path from %d to %d is %d\n",prev[curr], curr, c[prev[curr]][curr] - f[prev[curr]][curr]);
        best = min(best, c[prev[curr]][curr] - f[prev[curr]][curr]);
        curr = prev[curr];
    }
    assert(curr == s);
    return best;
}

void pump (int s, int t, int extra){
    int curr = t;
    while (prev[curr] != 0){
        f[prev[curr]][curr] += extra;
        f[curr][prev[curr]] -= extra;
        curr = prev[curr];
    }
    assert(curr == s);
}

int maxflow(int s, int t){
    for (int i = 0; i <= nodes; i++)
        for (int j = 0; j <= nodes; j++)
            f[i][j] = 0;
            
    int best = 0;
    while (true){
        // Find path between s and t
        if (!path(s, t)) break;
        // Find bottleneck
        int extra = bottleneck(s, t);
        // Pump flow
        pump(s, t, extra);
        // Add flow to best
        best += extra;
    }
            
    return best;
}

void print(){
    for (int i = 1; i <= nodes; i++){
        for (int j = 1; j <= nodes; j++){
            printf("%d ", c[i][j]);
        }
        printf("\n");
    }
}

int main(){
    int run = 1;
    while (scanf("%d", &nodes) == 1){
        if (nodes == 0) break;
        
        // Refresh capacity and grah
        for (int i = 0; i <= nodes; i++){
            g[i].clear();
            for (int j = 0; j <= nodes; j++){
               c[i][j] = 0; 
            }
        }
        
        // Read graph
        int s, t, edges;
        scanf("%d %d %d", &s, &t, &edges);
        for (int i = 0; i < edges; i++){
            int n1, n2, cap;
            scanf("%d %d %d", &n1, &n2, &cap);
            connect(n1, n2, cap);
        }
        
        // Print answer
        printf("Network %d\n", run++);
        printf("The bandwidth is %d.\n\n", maxflow(s, t););
        
    }
    return 0;
}