POJ 2391 - Ombrophobic Bovines

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

概要

\(F\) 個のファームがあり、各ファームには牛が \(c_i\) 頭おり、\(s_i\) 頭まで入れるシェルターがある。 \(P\) 本の道がファーム間を双方向に繋いでおり、各道を通るには \(t_j\) だけ時間がかかる。

すべての牛がシェルターに入るまでに必要な最小の時間を答える。 シェルターに入れない牛がいる場合は -1 を答える。

制約

解法

最小の時刻 \(T\) に関して二分探索 + 最大流。 POJ 2112 - Optimal Milking と同じ。 ただしこっちでは最大流のアルゴリズムに dinic を使った。

  1 #include <cstdio>
  2 #include <queue>
  3 #include <limits>
  4 #include <algorithm>
  5 using namespace std;
  6 static const long long INF = 1LL<<60;
  7 static const int MAXF = 200;
  8 
  9 int F, P;
 10 long long dist[MAXF][MAXF];
 11 int initial_cows[MAXF];
 12 int shelter[MAXF];
 13 
 14 static const int MAXN = 2*MAXF+2;
 15 
 16 template <class T>
 17 T dinic_augment(const T capacity[MAXN][MAXN], int N, T flow[MAXN][MAXN], int level[MAXN], bool finished[MAXN], int u, int sink, T cur)/*{{{*/
 18 {
 19   if (u == sink || cur == 0) {
 20     return cur;
 21   }
 22   if (finished[u]) {
 23     return 0;
 24   }
 25   finished[u] = true;
 26   for (int v = 0; v < N; v++) {
 27     if (capacity[u][v] - flow[u][v] > 0 && level[v] > level[u]) {
 28       const T f = dinic_augment(capacity, N, flow, level, finished, v, sink, min(cur, capacity[u][v] - flow[u][v]));
 29       if (f > 0) {
 30         flow[u][v] += f;
 31         flow[v][u] -= f;
 32         finished[u] = false;
 33         return f;
 34       }
 35     }
 36   }
 37   return 0;
 38 }/*}}}*/
 39 
 40 // O(V^2 E)
 41 template <typename T>
 42 T dinic(const T capacity[MAXN][MAXN], int N, int source, int sink)/*{{{*/
 43 {
 44   static T flow[MAXN][MAXN];
 45   for (int i = 0; i < N; i++) {
 46     fill_n(flow[i], N, 0);
 47   }
 48   T max_flow = 0;
 49 
 50   while (true) {
 51     static int level[MAXN];
 52     fill_n(level, N, -1);
 53     level[source] = 0;
 54     queue<int> q;
 55     q.push(source);
 56 
 57     int d = N;
 58     while (!q.empty() && level[q.front()] < d) {
 59       const int u = q.front();
 60       q.pop();
 61 
 62       if (u == sink) {
 63         d = level[u];
 64       }
 65       for (int v = 0; v < N; v++) {
 66         if (level[v] < 0 && capacity[u][v] - flow[u][v] > 0) {
 67           q.push(v);
 68           level[v] = level[u] + 1;
 69         }
 70       }
 71     }
 72 
 73     static bool finished[MAXN];
 74     fill_n(finished, MAXN, false);
 75     bool updated = false;
 76     while (true) {
 77       const T f = dinic_augment(capacity, N, flow, level, finished, source, sink, INF);
 78       if (f == 0) {
 79         break;
 80       }
 81       max_flow += f;
 82       updated = true;
 83     }
 84 
 85     if (!updated) {
 86       break;
 87     }
 88   }
 89 
 90   return max_flow;
 91 }/*}}}*/
 92 
 93 bool ok(long long limit)
 94 {
 95   const int source = 2*F, sink = 2*F+1;
 96   const int N = 2*F+2;
 97   static long long capacity[MAXN][MAXN];
 98   for (int i = 0; i < N; i++) {
 99     fill_n(capacity[i], N, 0);
100   }
101 
102   for (int i = 0; i < F; i++) {
103     for (int j = 0; j < F; j++) {
104       if (dist[i][j] <= limit) {
105         capacity[i][F+j] = INF;
106       } else {
107         capacity[i][F+j] = 0;
108       }
109     }
110   }
111   long long total = 0;
112   for (int i = 0; i < F; i++) {
113     capacity[source][i] = initial_cows[i];
114     capacity[F+i][sink] = shelter[i];
115     total += initial_cows[i];
116   }
117   return dinic(capacity, N, source, sink) == total;
118 }
119 
120 int main()
121 {
122   scanf("%d %d", &F, &P);
123   int cows = 0, shels = 0;
124   for (int i = 0; i < F; i++) {
125     scanf("%d %d", &initial_cows[i], &shelter[i]);
126     cows += initial_cows[i];
127     shels += shelter[i];
128   }
129   for (int i = 0; i < F; i++) {
130     fill_n(dist[i], F, INF);
131     dist[i][i] = 0;
132   }
133   for (int i = 0; i < P; i++) {
134     int u, v;
135     long long d;
136     scanf("%d %d %lld", &u, &v, &d);
137     --u;  --v;
138     dist[u][v] = min(dist[u][v], d);
139     dist[v][u] = min(dist[v][u], d);
140   }
141 
142   for (int k = 0; k < F; k++) {
143     for (int i = 0; i < F; i++) {
144       for (int j = 0; j < F; j++) {
145         dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
146       }
147     }
148   }
149 
150   long long hi = INF, lo = 0;
151   while (lo < hi) {
152     const long long mid = (lo + hi)/2LL;
153     if (ok(mid)) {
154       hi = mid;
155     } else {
156       lo = mid+1;
157     }
158   }
159   if (lo == INF) {
160     puts("-1");
161   } else {
162     printf("%lld\n", lo);
163   }
164   return 0;
165 }
poj/2391.cc