#include<stdio.h>
#include<string.h>
#define inf 100001
#define max 1000
#define white 0
#define black 1
int cap[max][max];
int flow[max][max],f[max],father[max],lujing[max];
int n,dui[100100],s,t;
int  bfs()
{
	int front,rear,i,number,sum,min,x,y;
	for(;;)
	{
		//printf("linger");
		y=t;
		x=s;
		front=0,rear=0;
		memset(f,white,sizeof(f));
		for(i=0;i<102;i++)
		{
			father[i]=-1;
		}
		father[x]=-1;
		f[x]=black;
		dui[front]=x;
		front++;
		while(rear!=front)
		{
			x=dui[rear];
			rear++;
			for(i=0;i<=n+1;i++)
			{
				if(cap[x][i]>0&&f[i]==white)
				{
					dui[front]=i;
					f[i]=black;
					front++;
					father[i]=x;
				}
			}
			if(f[t]==black)
				break;
		}
	
		if(father[y]==-1)
		{
				break;
		}
		number=0;
		lujing[number]=y;
		while(father[y]!=-1)
		{
			number++;
			lujing[number]=father[y];
			y=father[y];
		}//经过这个循环，路径已经存在于lujing数组里，数组里记录的是顶点
		min=inf;
		for(i=0;i<number;i++)
		{
			if(cap[lujing[i+1]][lujing[i]]<min)
			{
				min=cap[lujing[i+1]][lujing[i]];
			}
		}
		for(i=0;i<number;i++)
		{
			flow[lujing[i+1]][lujing[i]]+=min;
			flow[lujing[i]][lujing[i+1]]=0-(flow[lujing[i+1]][lujing[i]]);
		}
		for(i=0;i<number;i++)
		{
			cap[lujing[i+1]][lujing[i]]=cap[lujing[i+1]][lujing[i]]-min;
			//反向还有变化，待续；
			//cap[lujing[i]][lujing[i+1]]+=flow[lujing[i]][lujing[i+1]];
			cap[lujing[i]][lujing[i+1]]=cap[lujing[i]][lujing[i+1]]-min;
		}
		
	}
	sum=0;
	for(i=0;i<n;i++)
	{
		if(flow[i][y]>0)
		{
			sum=sum+flow[i][y];
		}
	}
	return sum;
	
	
}
int main()
{
	int np,nc,m,i,j;
	int d1,d2,d3,d4,d5,d6,d7;
	for(;scanf("%d %d %d %d",&n,&np,&nc,&m)!=EOF;)
	{
		getchar();
		s=n;
		t=n+1;
		memset(cap,0,sizeof(cap));
		memset(flow,0,sizeof(flow));
		for(i=0;i<m;i++)
		{
			scanf("(%d,%d)%d ",&d1,&d2,&d3);
			//getchar();
			if(d1==d2) continue;
			cap[d1][d2]=d3;
		}
		for(i=0;i<np;i++)
		{
			
			scanf("(%d)%d ",&d4,&d5);
			//getchar();
			cap[s][d4]=d5;//n是源点
		}
		for(i=0;i<nc;i++)
		{
			scanf("(%d)%d",&d6,&d7);
			if(i<nc-1)  getchar();
			cap[d6][t]=d7;//n+1是汇点
		}
		
	//printf("\n\n");
		printf("%d\n",bfs());
	}
	return 0;
}

• Re:广搜寻找增广路径为什么总是超时呢？附代码，拜托哪位大牛指点指点 (2463) 20111970 2012-08-12 17:01:35
• Re:广搜寻找增广路径为什么总是超时呢？附代码，拜托哪位大牛指点指点 (2463) 201341286 2015-08-05 11:44:04
  • Re:广搜寻找增广路径为什么总是超时呢？附代码，拜托哪位大牛指点指点 (48) 201341286 2015-08-05 11:45:01