POJ 3498 - March of the Penguins

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

概要

N 個の氷塊の上にペンギンがいる． ペンギンは距離 D までの氷塊に飛び移ることができる．

i 番目の氷塊は座標 (x[i], y[i]) にあり，最初にペンギンが n[i] 頭乗っている． 氷塊は脆いので，i 番目の氷塊からジャンプできるのは m[i] 回までである． 氷塊に着地するときは関係無い．

すべてのペンギンがある1つの氷塊に辿りつけるような氷塊をすべて出力する． ただし，そのような氷塊が1つも無い場合は -1 を出力する．

制約

解法

i 番目の氷塊にすべてのペンギンが来れるかどうかは，ジャンプの回数を容量として表現したグラフ上で i 番目の氷塊への最大流がペンギンの頭数に一致するかどうかでわかる．

これをすべての i に関して調べればよい．

N 回最大流を解くことになるため，TL が 8000MS とはいえ高速に求める必要がある． Edmonds-Karp だと TLE だったが，Dinic だと間に合った (3469MS)．

  1 #include <cstdio>
  2 #include <queue>
  3 #include <algorithm>
  4 using namespace std;
  5 static const int M = 210;
  6 static const int INF = 1000000;
  7 
  8 template <class T>
  9 T augment(const T capacity[M][M], int N, T flow[M][M], int level[M], bool finished[M], int u, int sink, T cur)
 10 {
 11   if (u == sink || cur == 0) {
 12     return cur;
 13   }
 14   if (finished[u]) {
 15     return 0;
 16   }
 17   finished[u] = true;
 18   for (int v = 0; v < N; v++) {
 19     if (capacity[u][v] - flow[u][v] > 0 && level[v] > level[u]) {
 20       const T f = augment(capacity, N, flow, level, finished, v, sink, min(cur, capacity[u][v] - flow[u][v]));
 21       if (f > 0) {
 22         flow[u][v] += f;
 23         flow[v][u] -= f;
 24         finished[u] = false;
 25         return f;
 26       }
 27     }
 28   }
 29   return 0;
 30 }
 31 
 32 template <typename T>
 33 T dinic(const T capacity[M][M], int N, int source, int sink)/*{{{*/
 34 {
 35   static T flow[M][M];
 36   for (int i = 0; i < N; i++) {
 37     fill_n(flow[i], N, 0);
 38   }
 39   T max_flow = 0;
 40 
 41   while (true) {
 42     static int level[M];
 43     fill_n(level, N, -1);
 44     level[source] = 0;
 45     queue<int> q;
 46     q.push(source);
 47 
 48     int d = N;
 49     while (!q.empty() && level[q.front()] < d) {
 50       const int u = q.front();
 51       q.pop();
 52 
 53       if (u == sink) {
 54         d = level[u];
 55       }
 56       for (int v = 0; v < N; v++) {
 57         if (level[v] < 0 && capacity[u][v] - flow[u][v] > 0) {
 58           q.push(v);
 59           level[v] = level[u] + 1;
 60         }
 61       }
 62     }
 63 
 64     static bool finished[M];
 65     fill_n(finished, M, false);
 66     bool updated = false;
 67     while (true) {
 68       const T f = augment(capacity, N, flow, level, finished, source, sink, INF);
 69       if (f == 0) {
 70         break;
 71       }
 72       max_flow += f;
 73       updated = true;
 74     }
 75 
 76     if (!updated) {
 77       break;
 78     }
 79   }
 80 
 81   return max_flow;
 82 }/*}}}*/
 83 
 84 inline double dd(const pair<int,int>& a, const pair<int,int>& b)
 85 {
 86   const int x = a.first - b.first;
 87   const int y = a.second - b.second;
 88   return x*x + y*y;
 89 }
 90 
 91 int main()
 92 {
 93   int T;
 94   scanf("%d", &T);
 95   while (T-- > 0) {
 96     int N;
 97     double D;
 98     scanf("%d %lf", &N, &D);
 99     const int source = 2*N;
100     const int sink = source + 1;
101     static int capacity[M][M];
102     for (int i = 0; i < 2*N+2; i++) {
103       fill_n(capacity[i], 2*N+2, 0);
104     }
105     static pair<int,int> ps[M];
106     int total = 0;
107     for (int i = 0; i < N; i++) {
108       int x, y, n, m;
109       scanf("%d %d %d %d", &x, &y, &n, &m);
110       total += n;
111       capacity[source][i] = n;
112       capacity[i][i+N] = m;
113       ps[i] = make_pair(x, y);
114     }
115     for (int i = 0; i < N; i++) {
116       for (int j = i+1; j < N; j++) {
117         if (dd(ps[i], ps[j]) < D*D) {
118           capacity[i+N][j] = INF;
119           capacity[j+N][i] = INF;
120         }
121       }
122     }
123 
124     bool first = true;
125     for (int i = 0; i < N; i++) {
126       capacity[i][sink] = INF;
127       const int r = dinic(capacity, 2*N+2, source, sink);
128       if (r == total) {
129         if (!first) {
130           putchar(' ');
131         }
132         printf("%d", i);
133         first = false;
134       }
135       capacity[i][sink] = 0;
136     }
137     if (first) {
138       puts("-1");
139     } else {
140       putchar('\n');
141     }
142   }
143   return 0;
144 }
poj/3498.cc