00820 - Internet Bandwidth

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    for(int n, s, t, c, cnt=0; scanf("%d", &n) && n && scanf("%d%d%d", &s, &t, &c);)
    {
        int C[101][101]={}, F[101][101]={}, f=0;

        for(int x, y, z; c-- && scanf("%d%d%d", &x, &y, &z);)
            C[x][y]+=z, C[y][x]+=z;

        while(1)
        {
            int P[101], M[101]={};
            memset(P, -1, 404);
            P[s]=-2, M[s]=1e9;
            queue<int> q;
            q.push(s);

            while(!q.empty() && !M[t])
            {
                int p=q.front();
                q.pop();

                for(int i=1; i<=n; i++)
                    if(C[p][i]>F[p][i] && P[i]==-1)
                        q.push(i), P[i]=p, M[i]=min(M[p], C[p][i]-F[p][i]);
            }
            if(M[t]==0) break;
            f+=M[t];

            for(int i=t, j=P[i]; i!=s; j=P[i=j])
                F[j][i]+=M[t], F[i][j]-=M[t];
        }
        printf("Network %d\nThe bandwidth is %d.\n\n", ++cnt, f);
    }
}