POJ 1459(최대 흐름)

//    ：   （   、   ）      

//    ：             ,  ISAP    ，                  

#include <iostream>

#include <queue>

//#include <conio.h>

using namespace std;

#define arraysize 205

int maxData = 0x7fffffff;

int capacity[arraysize][arraysize];     //    ，        

int pre[arraysize];                     //   

int num[arraysize];                     //num[i]     i       

int d[arraysize];                       //       

int n,np,nc,m;                          

void init(int src,int des)              //BFS    ，  t   0

{

     int i,j;

     queue<int> myqueue;

     myqueue.push(des);

     memset(num,0,sizeof(num));

     //memset(d,1,sizeof(d));

     for(i=0;i<n+2;++i)      //             

        d[i] = maxData;

     d[des] = 0;             //        0 

     num[0] = 1;

     int frontint;

     while(!myqueue.empty())  

     {

         frontint = myqueue.front();myqueue.pop();

         for(i=0;i<n+2;++i)

         {

             if(d[i]>=n+2 && capacity[i][frontint]>0)   //       ，  frontint            

             {

                 d[i] = d[frontint]+1;

                 myqueue.push(i);  

                 num[d[i]]++;     

             }                  

         }

     }

}

int findarc(int t)              //      

{

    int i,j;

    for(i=0;i<n+2;++i)

    {

        if(capacity[t][i]>0 && d[t]==d[i]+1) return i;

    }

    return -1;

}

int relabel(int t)              //     

{

    int i,j;

    //int mm = INT_MAX;

    int mm = maxData;

    for(i=0;i<n+2;++i)

    {

        if(capacity[t][i]>0) mm = min(mm,d[i]+1); 

    }

    return mm==maxData?(n+2):mm;

}

int maxFlow(int src,int des)

{

    int sumflow = 0;

    int delta;

    int i=src;      //       

    int j;

    memset(pre,-1,sizeof(pre));    

    while(d[src]<n+2)

    {

       j = findarc(i);

       if(j>=0)

       {

           pre[j] = i;

           i = j;            //      

           if(i==des)        //         

           {

               delta = maxData;

               for (i=des;i!=src;i=pre[i]) delta=min(delta,capacity[pre[i]][i]);  //             

               for (i=des;i!=src;i=pre[i]) capacity[pre[i]][i] -= delta, capacity[i][pre[i]] += delta; //       

               sumflow += delta;

           }

       }

       else

       {

           int x = relabel(i);

           num[x]++;

           num[d[i]]--;

           if(num[d[i]]==0) return sumflow;    //     

           d[i] = x;

           if(i!=src) i =pre[i];           

       }

    }

    return sumflow;

}

int main()

{

    //freopen("1.txt","r",stdin);

    int i,j;

    int start,end,weight;

    char tempchar;

    //             

    while(cin>>n>>np>>nc>>m)

    {

        memset(capacity,0,sizeof(capacity));

        //                  

        for(i=0;i<m;++i)

        {

            cin>>tempchar>>start>>tempchar>>end>>tempchar>>weight;

            capacity[start][end] = weight;            

        }

        for(i=0;i<np;++i)

        {

            cin>>tempchar>>end>>tempchar>>weight;

            capacity[n+1][end]= weight;          //n+1                  

        }

        for(i=0;i<nc;++i)

        {

            cin>>tempchar>>start>>tempchar>>weight;

            capacity[start][n]= weight;            //n       

        }

        init(n+1,n);            //      

        int result = maxFlow(n+1,n);        //       

        cout<<result<<endl;

    }

    /*  scanf      

    while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)

    {

        memset(r,0,sizeof(r));

        for(i=1;i<=m;i++)

        {

            scanf(" (%d,%d)%d",&a,&b,&z);

            r[a][b]=z;

        }

        for(i=1;i<=np;i++)

        {

            scanf(" (%d)%d",&a,&z);

            r[n][a]=z;

        }

        for(i=1;i<=nc;i++)

        {

            scanf(" (%d)%d",&a,&z);

            r[a][n+1]=z;

        }

        init(n+1,n);

        printf("%d
",maxFlow(n+1,n));

    }*/

    //getch();

    return 0;

}