> #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:广搜寻找增广路径为什么总是超时呢？附代码，拜托哪位大牛指点指点 (48) 201341286 2015-08-05 11:45:01