UVa 820 Internet Bandwidth Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
int n,s,t,c,mf,f;
vector<vector<int> > res;
vector<int> p;
void augment(int u,int flow){
    if(u==s){
        f=flow;
        return;
    }
    if(p[u]==-1)
        return;
    augment(p[u],min(flow,res[p[u]][u]));
    res[p[u]][u]-=f;
    res[u][p[u]]+=f;
}
int main(){
    int net=1;
    while(1){
        cin>>n;
        if(!n){
            // cout<<endl;
            return 0;
        }
        cin>>s>>t>>c;
        mf=0;
        res.assign(n+1,vector<int>(n+1,0));
        for(int i=0;i<c;i++){
            int x,y,w;
            cin>>x>>y>>w;
            res[x][y]+=w,res[y][x]+=w;
        }
        while(1){
            f=0;
            p.assign(n+1,-1);
            p[s]=s;
            queue<int> q;
            q.push(s);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                if(u==t)
                    break;
                for(int i=1;i<=n;i++){
                    if(res[u][i]>0&&p[i]==-1)
                        q.push(i),p[i]=u;
                }
            }
            augment(t,1001);
            if(!f)
                break;
            mf+=f;
        }
        cout<<"Network "<<net++<<endl;
        cout<<"The bandwidth is "<<mf<<'.'<<endl<<endl;
    }
    return 0;
}

Comments