[UVa] 820 Internet Bandwidth_dfs.cpp

#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 99999999

int flow[101][101];
int cap[101][101];
bool vis[101];
int pre[101];

bool DFS(int cur, const int &t, const int &n);
int FindFlow(int s, int t, int n);

int main()
{
    int n, s, t, c, Case = 1;
    while (scanf("%d", &n) && n) {
        // Initial
        for (int i = 1; i <= n; ++i) {
            fill(flow[i], flow[i]+n+1, 0);
            fill(cap[i], cap[i]+n+1, 0);
        }
        // Input
        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[a][b] += bandwidth;
            cap[b][a] = cap[a][b];
        }
        // FordFulkerson
        int result = 0;
        while (1) {
            fill(vis, vis+n+1, 0);
            if (!DFS(s, t, n)) break;
            result += FindFlow(s, t, n);
        }
        // Output
        printf("Network %d\n", Case++);
        printf("The bandwidth is %d.\n\n", result);
    }
}
bool DFS(int cur, const int &t, const int &n)
{
    vis[cur] = true;
    if (cur == t) return true;

    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;

        if (cap[cur][i] > flow[cur][i] || flow[i][cur] > 0) {
            pre[i] = cur;
            if (DFS(i, t, n))
                return true;
        }
    }
    return false;
}
int FindFlow(int s, int t, int n)
{
    int bottleneck = INF;
    int p;
    for (int i = t; i != s; i = pre[i]) {
        p = pre[i];
        if (cap[p][i] > flow[p][i])
            bottleneck = min(bottleneck, cap[p][i] - flow[p][i]);
        else
            bottleneck = min(bottleneck, flow[i][p]);
    }
    for (int i = t; i != s; i = pre[i]) {
        p = pre[i];
        if (cap[p][i] > flow[p][i])
            flow[p][i] += bottleneck;
        else
            flow[i][p] -= bottleneck;
    }
    return bottleneck;
}