[UVa] 820 Internet Bandwidth_bfs.cpp

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int cap[101][101];
int flow[101][101];
int bottleneck[101], pre[101];
int bfs(int N, int S, int T);

int main()
{
    int N, S, T, C, Case = 1;
    while (scanf("%d", &N) && N) {
        for (int i = 1; i <= N; ++i) {
            fill(cap[i], cap[i]+N+1, 0);
            fill(flow[i], flow[i]+N+1, 0);
        }
        scanf("%d %d %d", &S, &T, &C);
        int a, b, bandwidth;
        for (int i = 0; i < C; ++i) {
            scanf("%d %d %d", &a, &b, &bandwidth);
            cap[b][a] = (cap[a][b] += bandwidth);
        }
        printf("Network %d\n", Case++);
        printf("The bandwidth is %d.\n\n", bfs(N, S, T));
    }
}
int bfs(int N, int S, int T)
{
    int result = 0;
    while (1) {
        fill(bottleneck, bottleneck+N+1, 0);
        queue<int> Q;
        Q.push(S);
        bottleneck[S] = 999999999;

        while (!Q.empty() && bottleneck[T] == 0) {
            int cur = Q.front(); Q.pop();
            for (int nxt = 1; nxt <= N; ++nxt) {
                if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
                    Q.push(nxt);
                    pre[nxt] = cur;
                    bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
                }
            }
        }
        if (bottleneck[T] == 0) break;

        for (int cur = T; cur != S; cur = pre[cur]) {
            flow[pre[cur]][cur] += bottleneck[T];
            flow[cur][pre[cur]] -= bottleneck[T];  // opposite edge
        }
        result += bottleneck[T];
    }
    return result;
}