UVA 820 - Internet Bandwidth

這才是重點 "Print a blank line after each test case."

#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
struct{ int a, b, val; }es[10001]; int ecnt;
vector<int> to[1000];
int _n;
void init(int n){
    ecnt = 0;
    _n = n;
    for(int lx = 0;lx <= n;lx++)
        to[lx].clear();
    return;
}
void add_edge(int a, int b, int ab, int ba){
    es[ecnt].a = a, es[ecnt].b = b, es[ecnt].val = ab; to[a].push_back(ecnt++);
    es[ecnt].a = b, es[ecnt].b = a, es[ecnt].val = ba; to[b].push_back(ecnt++);
    return;
}
int from[1000];
int vis[1000];
int que[1000];
int path[1000]; int pathcnt;
int bfs(int s, int t){
    int n = _n;
    for(int lx = 0;lx <= n;lx++)
        vis[lx] = 0, from[lx] = -1;
    int qs = 0, qt = 1;
    que[0] = s; vis[s] = 1;
    while(qs < qt){
        int g = que[qs++];
        for(int lx = 0;lx < to[g].size();lx++){
            int lind = to[g][lx];
            int pind = es[lind].b;
            if(vis[pind]) continue;
            if(es[lind].val <= 0) continue;
            from[pind] = lind;
            vis[pind] = 1;
            que[qt++] = pind;
        }
    }
    if(vis[t] == 0) return 0;
    pathcnt = 0;
    int pp = t;
    int min_val = 100000;
    while(pp != s){
        int lid = from[pp];
        //printf("%d ~ %d at %d\n", es[lid].a, es[lid].b, es[lid].val);
        path[pathcnt++] = lid;
        min_val = min(es[lid].val, min_val);
        pp = es[lid].a;
    }
    for(int lx = 0;lx < pathcnt;lx++){
        int lind = path[lx];
        es[lind].val -= min_val;
        es[lind^1].val += min_val;
    }
    return min_val;
}
int Ekarp(int s, int t){
    int f = 0, df;
    for(;;){
        //printf("============\n");
        df = bfs(s, t);
        if(df == 0) break;
        f += df;
    }
    return f;
}
int main()
{
    int n; int cs = 0;
    for(;;){
        cs++;
        scanf("%d", &n);
        if(n == 0) break;
        init(n);
        int s, t, c; scanf("%d %d %d", &s, &t, &c);
        int mat[101][101] = {0};
        while(c--){
            int a, b, val;
            scanf("%d %d %d", &a, &b, &val);
            mat[a][b] += val;
            mat[b][a] += val;
        }
        for(int lx = 1;lx <= n;lx++)
            for(int ly = lx+1;ly <= n;ly++)
                if(mat[lx][ly])
                    add_edge(lx,ly,mat[lx][ly], mat[lx][ly]);
        printf("Network %d\n", cs);
        printf("The bandwidth is %d.\n\n", Ekarp(s, t));
    }
    return 0;
}