网络流模板略去
int K,C,M;
const int MAX = 300;
const int INF = 1e8;
int G[MAX][MAX];
void floyd()
{
	for(int k = 1;k <= K+C;k++)
		for(int i = 1;i <= K+C;i++)
			for(int j = 1;j <= K+C;j++)
				G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
}
int main()
{
	scanf("%d%d%d",&K,&C,&M);
	for(int i = 1;i <= K + C;i++)
	{
		for(int j = 1;j <= K + C;j++)
		{
			int t;scanf("%d",&t);
			if(!t) t = INF;
			G[i][j] = t;
		}
	}
	floyd();
	int l = 1,r = 1;
	for(int i = 1;i <= K;i++)
		for(int j = K + 1;j <= K + C;j++)
			r = max(r,G[i][j]);
	r++;
	while(r > l)
	{
		int mid = (l+r)/2;
		prepare(K+C+2,0,K+C+1);
		for(int i = 1;i <= K;i++)//构图
			for(int j = K+1;j<=K+C;j++)
				if(G[i][j] <= mid) 
					addedge(i,j,1);
		for(int i = 1;i <= K;i++)
			addedge(0,i,M);
		for(int i = K+1;i <= K+C;i++)
			addedge(i,K+C+1,1);
		int f = Dinic_flow();
		if(f < C) l = mid + 1;
		else r = mid;
	}
	cout<<l<<endl;
}

• 贼？ (6) KatrineYang 2017-03-20 02:25:56