UVa 820 - Internet Bandwidth Solution

#include<iostream>
#include<cstdio>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
#include<deque>
#include<iterator>
#include<assert.h>
#include<bitset>
#include<climits>
#include<ctime>
#include<complex>

using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define PB push_back
#define PI acos(-1.0)
#define MP(a,b) make_pair(a,b)
#define PII pair<int,int>
#define PCC pair<char,char>
#define PIC pair<int,char>
#define PCI pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define VC vector<char>
#define max3(a,b,c) max(a,max(b,c)
#define min3(a,b,c) min(a,min(b,c)
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define For(i,a) for(int i=0;i<a;i++)

#define S(a) scanf("%d",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define S3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define SLL(a) scanf("%lld",&a)
#define SLL2(a,b) scanf("%lld%lld",&a,&b)
#define SLL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define SS(a) scanf("%s",a)
#define SC(a) scanf("%c",&a)
#define SD(a) scanf("%lf",&a)
#define P(a) printf("%d",a)
#define PLL(a) printf("%lld",a)
#define PD(a) printf("%lf",a)
#define PC(a) printf("%c",a)
#define PS(a) printf("%s",a)
#define KS printf("Case %d: ",kk++)
#define KN printf("Case %d:\n",kk++)
#define KH printf("Case #%d: ",kk++)
#define NL printf("\n")
#define DB cout<<"done"<<endl;

#define EPS 1e-9
#define MOD 1000000007
#define INF INT_MAX/3
#define MX 100010

template<typename T>inline string tostring(T a){ostringstream os("");os << a;return os.str();}
template<typename T>inline LL tolong(T a){LL res;istringstream os(a);os>>res;return res;}
template<typename T>inline VI parse(T str){VI res;int s;istringstream os(str);while(os>>s)res.PB(s);return res;}
template< class T > inline T _sqrt(T x) { return (T) sqrt( (double) x); }
template< class T > inline T _bigmod(T n,T m) {T ans=1,mult=n%MOD; while(m){ if(m & 1) ans=(ans*mult)%MOD; m>>=1; mult=(mult*mult)%MOD; } ans%=MOD; return ans;}
template< class T > inline T _modinv(T x) {return _bigmod(x,(T) MOD-2)%MOD;}
inline int LEN(string a) {return a.length();}
inline int LEN(char a[]) {return strlen(a);}
template<class T> inline T _gcd(T a, T b){return (b.chk()==0) ? a : _gcd(b, a % b);}
template< class T > inline T _lcm(T x,T y) { return x*y/_gcd(x,y);}

int source,dest,cost[110][110],node,parent[110];
int bfs()
{
    int tmp,mn;
    queue<int>q;

    FOR(i,1,node)
        parent[i]=-2;
    parent[source]=-1;

    q.push(source);
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        if(tmp==dest)
        {
            mn=INF;
            int i=dest;
            while(parent[i]!=-1)
            {
                mn=min(mn,cost[parent[i]][i]);
                i=parent[i];
            }
            return mn;
        }

        FOR(i,1,node)
            if(cost[tmp][i] && parent[i]==-2)
            {
                q.push(i);
                parent[i]=tmp;
            }
    }
    return 0;
}
int max_flow()
{
    int total=0,mn;
    while(1)
    {
        mn=bfs();
        if(!mn) break;
        total+=mn;

        int i=dest;
        while(parent[i]!=-1)
        {
            cost[parent[i]][i]-=mn;
            i=parent[i];
        }
    }

return total;
}


int main()
{
    int tc,kk=1,n,m,edge,u,v,cst;
    //cin>>tc;
    while(cin>>node)
    {
        if(node==0) break;
        //cin>>node;
        cin>>source>>dest>>edge;

        CLR(cost);

        For(i,edge)
        {
            cin>>u>>v>>cst;
            cost[u][v]+=cst;
            cost[v][u]+=cst;
        }

        int res=max_flow();
        //KS;
        cout<<"Network "<<kk++<<endl;
        cout<<"The bandwidth is ";
        cout<<res<<"."<<endl<<endl;
    }

return 0;
}