#include<stdio.h>
#include<string.h>
#define MM 250
const int inf = 1 << 30;
int K,C,M,z;
int cur[MM],pre[MM],dis[MM][MM],Dis[MM],gap[MM];
int maze[MM][MM];
int min(int a,int b)
{
	return a==-1||b>a?b:a;
}
void Froyd()
{
	int u,w,v,n=z;
	for(u=1;u<=n;u++)
	for(v=1;v<=n;v++)
		if(dis[v][u]!=inf)
		{
			for(w=1;w<=n;w++)
			if(dis[v][u]+dis[u][w]<dis[v][w])
			dis[v][w]=dis[v][u]+dis[u][w];
		}
		return ;
}
void build_graph(int max)
{
	int n=z+1,i,j;
	memset(maze,0,sizeof(maze));
	for(i=1;i<=K;i++)
	{
		maze[i][n]=M;
	}
	for(i=K+1;i<=z;i++)
	{
		maze[0][i]=1;
	}
	for(i=K + 1; i <= z; i ++)
          for(j = 1; j <= K; j ++)
              if(dis[i][j] <= max)//注意现在的dis已不是先前的dis现在以为最短路径
                   maze[i][j] = 1;
			  return ;
}
int sap(int s,int t,int nodenum)
{
	memset(cur,0,sizeof(cur));
	memset(pre,0,sizeof(pre));
	memset(Dis,0,sizeof(Dis));
	memset(gap,0,sizeof(gap));
	int u=pre[s]=s,maxflow=0,aug=-1;
	int v;
	gap[0]=nodenum;
	while(Dis[s]<nodenum)
	{
		loop:
		for(v=cur[u];v<nodenum;v++)
		{
			if(maze[u][v]&&Dis[u]==Dis[v]+1)
			{
				aug=min(aug,maze[u][v]);
				pre[v]=u;
				u=cur[u]=v;
				if(v==t)
				{
					maxflow+=aug;
					for(u=pre[v];v!=s;v=u,u=pre[u])
					{
						maze[u][v]-=aug;
						maze[v][u]+=aug;
					}
					aug=-1;
				}
				goto loop;
			}
		}

		int mindis=nodenum-1;
		for(v=0;v<nodenum;v++)
		{
			if(maze[u][v]&&mindis>Dis[v])
			{
				cur[u]=v;
				mindis=Dis[v];
			}
		}

		if((--gap[Dis[u]])==0)
			break;
		gap[Dis[u]=mindis+1]++;
		u=pre[u];
	}
	return maxflow;
}
int main()
{
	int i,j,left,right;
	scanf("%d%d%d",&K,&C,&M);
		z=K+C;
		for(i=1;i<=z;i++)
		{
			for(j=1;j<=z;j++)
			{
				scanf("%d",&dis[i][j]);
				if(dis[i][j]==0)
					dis[i][j]=inf;
			}
		}
		Froyd();
		left=0,right=10000;
		while(left<right)
		{
			int mid=(left+right)>>1;
			build_graph(mid);
			int temp=sap(0,z+1,z+2);
			if(temp>=C)right=mid;
			else left=mid+1;
		}
		printf("%d\n",right);
		return 0;
}

• Re:哪位好心人帮我看一下，检查了很长时间都还是wa！！天理啊。。。。 (2329) 671superone 2012-08-07 11:50:32