POJ 1273(ISAP+隣接表)

//    ：    

//    ：ISAP  （     ） 

#include<iostream>

#include<cstdio>

//#include<conio.h>

#include<string.h>

using namespace std;

const int maxn=201;   

const int maxm=201;

struct node

{

	int x,y,f,op,next;     //x  ，y  ,f  ,next  x         g    ,op     g       

}g[maxm*2];

//first[]     x             g     

//sumd[]         i        ，       

//now[]     x            g     

int first[maxn],now[maxn],sumd[maxn];    

int ncount;                                //        

int dis[maxn],fanhui[maxn],pre[maxn],tot; //dis[]        ,pre[i]  i    g[]    ,tot       

void add(int x,int y,int c)

{

     tot++;                   //tot       

     g[tot].x=x; 

     g[tot].y=y;    

     g[tot].f=c; 

     g[tot].op=tot+1;        //    g       

     g[tot].next=first[x];   //   x         g       

     first[x]=tot;           // x        

     tot++;            

     //   

     g[tot].x=y;

     g[tot].y=x; 

     g[tot].f=0;             //          0 

     g[tot].op=tot-1;

     g[tot].next=first[y]; 

     first[y]=tot;    

}

//ISAP  

int maxflow(int src,int des)             

{

	int i,flow,t,j,tempmin;   //i,j      ，t       g     

	bool flag;                //             

	int sumFlow;              

	memset(dis,0,sizeof(dis));      //   dis 0              

	memset(sumd,0,sizeof(sumd));

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

		now[i]=first[i];      

	sumd[0]=ncount;                 //   0    ncount  

    sumFlow=0;                      //sumFlow     ，    0 

	i=src;                          //i       

    flow=10000000;

	while(dis[src]<ncount)

	{

		fanhui[i]=flow;

		flag=false;     

		t=now[i];

		while(t!=0)           //      

		{

			j=g[t].y;

			if((g[t].f>0)&&(dis[j]+1==dis[i])) //     

			{

				flag=true;

				pre[j]=t;

				now[i]=t;

				if(g[t].f<flow)          //       

					flow=g[t].f;

				i=j;

				if(i==ncount)                 //       

				{

					sumFlow+=flow;

					while(i!=src)          //       

					{

						g[pre[i]].f-=flow;            //    

						g[g[pre[i]].op].f+=flow;      //    

						i=g[pre[i]].x;

					}

					flow=10000000;

				}

				break;

			}

			t=g[t].next;

		}

		if(flag)

			continue;

		//         

		tempmin=ncount-1;

		t=first[i];

		while(t!=0)

		{

			if((g[t].f>0)&&(dis[g[t].y]<tempmin))

			{

				tempmin=dis[g[t].y];

				now[i]=t;

			}

			t=g[t].next;

		}

		sumd[dis[i]]--;

		if(sumd[dis[i]]==0) break;           //     

		dis[i]=tempmin+1;		             //    +1,  d[i]=tempmin{d[j]+1|(i,j)      }

		sumd[dis[i]]++;

		if(i!=src)

		{

			i=g[pre[i]].x; 

			flow=fanhui[i];

		}

	}

	return sumFlow;

}

int main()

{

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

	int i,j;

	int N,M;

	int x,y,c;

	int src,des;     //src   ，des    

	while(scanf("%d%d",&N,&M)!=-1)

	{

        memset(first,0,sizeof(first));       //   first 

        src = 1;

        des = M;

        ncount = M;

        tot = 0;                             //tot    0 

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

        {

            cin>>x>>y>>c;

            add(x,y,c);

        } 

        printf("%d
",maxflow(src,des));           

    }    

	//getch();

	return 0;

}