UVA 820

#include <bits/stdc++.h>

using namespace std;

class Dinic{
    struct Edge{
        int to;
        int c;
        int flow;
    };

public:
    vector<Edge> edges;
    vector<vector<int>> g;
    vector<int> lvl;
    int s,t;
    const int INF = 100000;
    const int VCOUNT;

    Dinic(int VCOUNT) : VCOUNT(VCOUNT), g(VCOUNT), lvl(VCOUNT){}

    int addEdge(int u, int v, int cap){
        Edge dir = {v,cap,0};
        Edge aug = {u,cap,0};
        int ret = edges.size();
        g[u].push_back(edges.size());
        edges.push_back(dir);
        g[v].push_back(edges.size());
        edges.push_back(aug);
        return ret;
    }

    void clearAll(){
        for(auto &a : g)a.clear();
        edges.clear();
    }

    void clearFlow(){
        for(auto &e : edges)e.flow = 0;
    }

    bool BFS(){
        fill(lvl.begin(), lvl.end(), -1);
        queue<int> q;
        q.push(s);
        lvl[s] = 0;

        while(!q.empty()){
            int v = q.front(); q.pop();
            if(v == t) break;

            for(auto u : g[v]){
                Edge &e = edges[u];
                if(lvl[e.to] < 0 && e.flow < e.c){
                    lvl[e.to] = lvl[v] + 1;
                    q.push(e.to);
                }
            }
        }

        return lvl[t] != -1;
    }

    int DFS(int v, int minFlow){
        if(v == t || minFlow == 0) return minFlow;
        int flow = 0;

        for(auto adj : g[v]){
            Edge &e = edges[adj];
            if(lvl[e.to] == lvl[v]+1 && e.flow < e.c){
                int ret = DFS(e.to, min(minFlow, e.c - e.flow));
                if(ret > 0){
                    e.flow += ret;
                    edges[adj^1].flow -= ret;
                    flow += ret;
                    minFlow -= ret;
                    if(minFlow <= 0)break;
                }
            }
        }

        return flow;
    }

    int maxFlow(int s, int t){
        this->s = s;
        this->t = t;

        int mf = 0;
        while(BFS()){
            int f = DFS(s, INF);
            mf += f;
            if(f == 0) break;
        }

        return mf;
    }
};

int main(){
    //ios_base::sync_with_stdio(false);cin.tie(NULL);

    int v;
    int it = 1;
    while(cin >> v, v){
        int s,t,c;
        cin >> s >> t >> c;
        Dinic d(v+1);

        while(c-->0){
            int x,y,cap;
            cin >> x >> y >> cap;
            d.addEdge(x,y,cap);
        }

        printf("Network %d\n", it++);
        printf("The bandwidth is %d.\n\n", d.maxFlow(s,t));
    }

    return 0;
}