1273.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#define NMAX 204
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int l[NMAX][NMAX]={0};
int next[NMAX][NMAX]={0};
int r[NMAX][NMAX]={0};
int org[NMAX][NMAX]={0};
bool f[NMAX];
typedef struct
{
	int from,cap;
}set;
set a[NMAX]={0};
bool flag[NMAX]={0};
int N,M,st,ed;
int q[NMAX*NMAX];
int max=0;
int min(int a,int b)
{
	return a<b?a:b;
}
void solve()
{
	int front,end;
	memcpy(org,l,sizeof(l));
	while(1)
	{
		memset(a,0,sizeof(a));
		front=end=0;
		a[st].cap=INF;
		q[end++]=st;
		int cp,np,flow;
		bool toend=0;
		memset(f,0,sizeof(f));
		f[st]=1;
		
		while(front<end)
		{
			cp=q[front++];
			int j=0;
			for(j=0;next[cp][j];j++)
			{
				np=next[cp][j];
				if(f[np])
					continue;
				flow=l[cp][np];
				
				if(!flow)
					continue;
				if(a[cp].cap<flow)
					flow=a[cp].cap;
				f[np]=1;
				a[np].cap=flow;
				a[np].from=cp;
				if(np==ed)
				{
					front=end=0;
					toend=1;
					break;
				}
				q[end++]=np;
			}

		}
		if(!toend)
			break;
		cp=ed;
		flow=a[cp].cap;
		while(cp!=st)
		{
			np=a[cp].from;
			l[np][cp]-=flow;
			l[cp][np]+=flow;
			cp=np;
		}
		memset(a,0,sizeof(a));
	}
	max=0;
	for(int i=1;i<=N;i++)
	{
		max+=l[ed][i];
	}
	
	printf("%d\n",max);
	

	
}
main()
{
#if _DEBUG 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(scanf("%d%d",&M,&N)!=EOF)
	{
		st=1,ed=N;
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(next,0,sizeof(next));
		memset(a,0,sizeof(a));
		int w,v,f,i,j;
		for(i=1;i<=M;i++)
		{
			scanf("%d%d%d",&w,&v,&f);
			l[w][v]+=f;
			j=0;
			while(next[w][j])j++;
			next[w][j]=v;
			j=0;
			while(next[v][j])j++;
			next[v][j]=w;
		}
		solve();
	}
#if _DEBUG 
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}