2112 Optimal Milking

問題概要

K台の搾乳機およびC頭の牛がいる。搾乳機はM頭の牛から乳を搾れる。
各牛と搾乳機の距離が与えられる。

各搾乳機にM頭以下の牛が割り当てられた状態になるよう牛が移動するとき、
最も移動距離の長い牛の移動距離の最小値を求めよ。

K≦30,M≦15,C≦300を満たす。また距離行列の各値は200である。

解法

牛はグラフを通って他のノードにも移動できるため、
最初にワーシャルフロイドして牛と搾乳機間の最短距離を求めておくことが必要。

求めたら、距離を決めつけて最大流。
距離mid以下の牛と搾乳機の間を辺で結び、フローを流せるだけ流して、牛の数の流量が流れるかみる。

Edmonds-Karpに辺を小さい順に足していき、順次増加パスを見つけてフローを流す方針だとなぜかWAだった……
二分探索だと通った。
各辺の長さは200以下であるので、mid番目の辺までで作れるグラフにフローを流すような二分探索よりも、長さmid以下の辺で作れるグラフにフローを流す二分探索のほうが得。

ソースコード

maximumFlowはspaghetti sourceのDinic.

void add(Graph &g,int s,int t,int w){
	g[s].pb(Edge(s,t,w)); g[t].pb(Edge(t,s,0));
}
int d[250][250];
int main(){
	int k,c,m; scanf("%d%d%d",&k,&c,&m);
	int n=k+c,far=0;
	rep(i,n)rep(j,n){
		scanf("%d",d[i]+j);
		if(i!=j&&!d[i][j])d[i][j]=INF;
	}
	rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	rep(i,n)rep(j,n)if(d[i][j]!=INF)far=max(far,d[i][j]);
	
	Graph g(n+2);
	rep(i,k)add(g,n,i,m);
	rep(i,c)add(g,k+i,n+1,1);
	
	int lo=0,hi=far,mid;
	while(lo+1<hi){
		mid=(lo+hi)/2;
		Graph h=g;
		rep(i,k)rep(j,c)if(d[i][k+j]<=mid)add(h,i,k+j,1);
		if(maximumFlow(h,n,n+1)==c)hi=mid; else lo=mid;
	}
	printf("%d\n",hi);
	
	return 0;
}