POJ 2112 - Optimal Milking

http://poj.org/problem?id=2112

概要

K 個の搾乳機と C 頭の牛がある． 各搾乳機は一日に M 頭の牛を処理できる．

どの牛もいずれかの搾乳機のところまで行かせるとき，牛が歩く必要のある最大の距離を最小化したい． そのときの距離を答える．

制約

解法

二分探索 + 最大流．

まず各ノード間の最短距離をワーシャルフロイドで求めておいて，最短距離が D 以下のエッジのみを使って条件を満たすように牛が移動できるかを判断して，D について二分探索．

条件を満たせるかどうかは，ソースから牛に1のエッジを張り，搾乳機からシンクに M の容量のエッジを張り，使えるエッジに無限大の容量を持たせたときの最大流が C 未満かどうかで判断できる．

  1 #include <cstdio>
  2 #include <limits>
  3 #include <queue>
  4 #include <algorithm>
  5 using namespace std;
  6 static const int MAX_N = 232;
  7 
  8 int edmonds_karp(const int capacity[MAX_N][MAX_N], int N, int source, int sink)/*{{{*/
  9 {
 10   static int flow[MAX_N][MAX_N];
 11   for (int i = 0; i < N; i++) {
 12     fill_n(flow[i], N, 0);
 13   }
 14   int max_flow = 0;
 15 
 16   while (true) {
 17     static int parent[MAX_N];
 18     fill_n(parent, N, -1);
 19     queue<int> q;
 20     q.push(source);
 21 
 22     while (!q.empty() && parent[sink] < 0) {
 23       const int v = q.front();
 24       q.pop();
 25 
 26       for (int u = 0; u < N; u++) {
 27         if (parent[u] < 0 && capacity[v][u] - flow[v][u] > 0) {
 28           parent[u] = v;
 29           if (u == sink) {
 30             break;
 31           }
 32           q.push(u);
 33         }
 34       }
 35     }
 36 
 37     if (parent[sink] < 0) {
 38       break;
 39     }
 40 
 41     int aug = numeric_limits<int>::max();
 42     for (int v = sink; v != source; v = parent[v]) {
 43       const int u = parent[v];
 44       aug = min(aug, capacity[u][v] - flow[u][v]);
 45     }
 46     max_flow += aug;
 47     for (int v = sink; v != source; v = parent[v]) {
 48       const int u = parent[v];
 49       flow[u][v] += aug;
 50       flow[v][u] -= aug;
 51     }
 52   }
 53 
 54   return max_flow;
 55 }/*}}}*/
 56 
 57 int main()
 58 {
 59   int K, C, M;
 60   scanf("%d %d %d", &K, &C, &M);
 61   const int N = K+C;
 62   static int g[MAX_N][MAX_N];
 63   for (int i = 0; i < N; i++) {
 64     for (int j = 0; j < N; j++) {
 65       scanf("%d", &g[i][j]);
 66       if (g[i][j] == 0) {
 67         g[i][j] = numeric_limits<int>::max()/N;
 68       }
 69     }
 70   }
 71 
 72   for (int k = 0; k < N; k++) {
 73     for (int i = 0; i < N; i++) {
 74       for (int j = 0; j < N; j++) {
 75         g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
 76       }
 77     }
 78   }
 79 
 80   // binary search
 81   int left = 0, right = 0;
 82   for (int i = 0; i < K; i++) {
 83     right = max(right, *max_element(g[i]+K, g[i]+K+C));
 84   }
 85   while (left < right) {
 86     const int mid = (left + right)/2;
 87     static int capacity[MAX_N][MAX_N];
 88     // N: source
 89     // N+1: sink
 90     for (int i = 0; i < K; i++) {
 91       capacity[N][i] = M;
 92       for (int j = K; j < K+C; j++) {
 93         capacity[j][N+1] = 1;
 94         if (g[i][j] <= mid) {
 95           capacity[i][j] = numeric_limits<int>::max();
 96         } else {
 97           capacity[i][j] = 0;
 98         }
 99       }
100     }
101 
102     const int max_flow = edmonds_karp(capacity, N+2, N, N+1);
103     if (max_flow < C) {
104       // ng. too short
105       left = mid+1;
106     } else {
107       // ok
108       right = mid;
109     }
110   }
111   printf("%d\n", left);
112   return 0;
113 }
poj/2112.cc