PKU 2112 Optimal Milking

[問題]
2112 -- Optimal Milking

牛とミルクマシーン(適当)が辺で接続されている。全ての牛をミルクマシーンに到着させたい。この時もっともたくさん歩く牛の距離を最小化せせよ。ただし、ミルクマシーンはm匹の牛しか処理できない。

[解法]
WarshallFloyd + 最大流 + 二分探索

ミルクマシーンの処理できる牛m匹という制約が無ければ単純な最短経路問題だが、この場合は最短経路では解けない。
なので
C(t):= 牛の歩く最大距離をt[m]以内にできる
とすると二分探索できる。
C(t)の判定は牛とミルクマシーンを頂点とし、下図のようなグラフの最大流を求める。

(中央の辺はCow - > Machineの最短路がt以下の距離の場合に張る)

Winのペイント見たいなお手軽なソフトないのかなw

const int MAX_V=1000;
int dist[MAX_V][MAX_V];
int k,c,m;

struct edge{int to,cap,rev;};
vector<edge>G[MAX_V];
bool used[MAX_V];

int V;

void warshall_floyd(){  
  for(int k = 1; k <= V; k++)
    for(int i = 1; i <= V; i++)
      if(dist[i][k] != INF)
	for(int j = 1; j <= V; j++)
	  dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
}

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size() - 1});  
}

int dfs(int v,int t,int f){
  if(v == t) return f;
  used[v]=true;
  for(int i = 0;i < G[v].size();i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
	e.cap -= d;
	G[e.to][e.rev].cap += d;
	return d;	
      }
    }
  }
  return 0; 
}

int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,INF);
    if(f == 0) return flow;
    flow += f;
  }
}

void Init(int time){
  memset(used,0,sizeof(used));
  rep(i,MAX_V) G[i].clear();
  for(int i= k + 1;i <= V;i++)
    add_edge(0,i,1);
  for(int i= 1;i <= k;i++)  
    add_edge(i,V + 1,m);
  
  for(int i= k + 1;i <= V;i++){
    for(int j= 1;j <= k;j++){
      if(dist[i][j] <= time){
	//	printf("%d,%d\n",i,j);
	add_edge(i,j,1);
      }
    }
  }
}


int main(){
  memset(dist,0,sizeof(dist));
  scanf("%d %d %d",&k,&c,&m);
  V = k + c;
  for(int i = 1; i <= V; i++){
    for(int j = 1; j <= V; j++){
      scanf("%d",&dist[i][j]);
      if(dist[i][j] == 0) dist[i][j] = INF;
    }
  }
  warshall_floyd();
  int l = 0,r = 10000;
  while(r - l > 1){
    int mid = (l + r) / 2;
    Init(mid);
    int flow = max_flow(0,V + 1);
    //    printf("%d %d\n",mid,flow);
    if(flow >= c) r = mid;
    else l = mid;
  }
  printf("%d\n",r);
}