PKU 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); }