#include<stdio.h>
#include<cstring>
#define MN    202
#define MZ    10000001
#define min(x,y)   (((x)<(y))?(x):(y)) 

int c[MN][MN],tmpf,flow,total ;
bool bvisit[MN] ;
int n,m ; 

bool Search( int x ){
	bvisit[x] = true ;
	if( x == n ){
		total += flow ; return true;
	}
    for( int y = 1; y <= n ; y ++ )
		if( c[x][y] > 0 && !bvisit[y] ){
			tmpf = flow ; flow = min(flow,c[x][y] );
			if( Search(y) ){
				c[x][y] -= flow ; c[y][x] += flow ; 
				return true ;
			}
			flow = tmpf ;
		}
	return false ;
}

int main(){
	int x,y,value ;
	freopen("in.txt","r",stdin) ;
	while( scanf("%d%d",&m,&n)!=EOF ){
		memset(c,0,sizeof(c)) ;	 total = 0 ; 
		while(m--){
			scanf("%d%d%d",&x,&y,&value) ;
			if( x!= y )c[x][y] += value; 
		} 		
 		while(1){
			flow = MZ ; memset(bvisit,false,sizeof(bvisit)) ;	
			if( Search(1) == false )break; 		 
		}
		printf("%d\n",total) ;
	}
	return 0 ;
}

• Re:第一道 最大流 哈哈 (1017) 851540201 2011-02-15 11:19:22