POJ 3343 - Against Mammoths

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

概要

人類は H 個の惑星を持っており，それぞれの惑星には最初 n[i] 個の宇宙船があり，さらに一年毎に m[i] 個の宇宙船を製造することができる．

一方エイリアンは A 個の惑星を持っており，同様にそれぞれの惑星には最初 n'[i] 頭のマンモスがおり，さらに一年毎に m'[i] 頭マンモスが増える．

このとき，人類がすべてのエイリアンの惑星を征服できる最小の年数を答える． ただし，征服できないときは「IMPOSSIBLE」と答える．

1つの惑星で作られた宇宙船はある時点で同時に1つの惑星へと向かい，宇宙船の数がマンモスの数以上だったときに征服できる． 複数の惑星から1つの惑星を攻めることはできないし，1つの惑星が複数の惑星を攻めることもできない．

惑星間には距離が設定されており，移動に Y[i][j] 年掛かる．移動中は当然宇宙船を製造することはできないが，その間もマンモスは増え続ける．

制約

解法

Y 年間で征服できるかどうかを判定しながら，Y に関して二分探索． 十分大きな Y で征服できないときは「IMPOSSIBLE」.

判定は，Y 年間で征服できる惑星にエッジを張った二部グラフの最大マッチングが A と等しいかどうかでわかる．

  1 #include <cstdio>
  2 #include <vector>
  3 using namespace std;
  4 static const int INF = 10000000;
  5 
  6 bool bm_augment(const vector<int> *g, int u, int *match_to, int *visited) // {{{
  7 {
  8   if (u < 0) {
  9     return true;
 10   }
 11 
 12   for (vector<int>::const_iterator it(g[u].begin()); it != g[u].end(); ++it) {
 13     if (!visited[*it]) {
 14       visited[*it] = true;
 15       if (bm_augment(g, match_to[*it], match_to, visited)) {
 16         match_to[u] = *it;
 17         match_to[*it] = u;
 18         return true;
 19       }
 20     }
 21   }
 22   return false;
 23 } // }}}
 24 
 25 int bipartite_matching(const vector<int> *g, int N)  // {{{
 26 {
 27   static int match_to[500];
 28   fill_n(match_to, N, -1);
 29   int match = 0;
 30   for (int u = 0; u < N; u++) {
 31     static int visited[500];
 32     fill_n(visited, N, 0);
 33     if (bm_augment(g, u, match_to, visited)) {
 34       match++;
 35     }
 36   }
 37   return match;
 38 } // }}}
 39 
 40 bool defeat(const pair<int,int>& human, const pair<int,int>& alien, int d, int T)
 41 {
 42   const int t = T - d;
 43   if (t < 0) {
 44     return false;
 45   }
 46   if (human.first - d*human.second >= alien.first) {
 47     const int h = human.first;
 48     const int a = alien.first + d*alien.second;
 49     return h >= a;
 50   } else {
 51     const long long h = human.first + static_cast<long long>(t)*human.second;
 52     const long long a = alien.first + static_cast<long long>(T)*alien.second;
 53     return h >= a;
 54   }
 55 }
 56 
 57 bool ok(const pair<int,int> *humans, int H, const pair<int,int> *aliens, int A, const int dist[250][250], int T)
 58 {
 59   static vector<int> g[500];
 60   for (int i = 0; i < A+H; i++) {
 61     g[i].clear();
 62   }
 63   for (int i = 0; i < H; i++) {
 64     for (int j = 0; j < A; j++) {
 65       if (defeat(humans[i], aliens[j], dist[i][j], T)) {
 66         g[i].push_back(H+j);
 67       }
 68     }
 69   }
 70   return bipartite_matching(g, A+H) == A;
 71 }
 72 
 73 int main()
 74 {
 75   int H, A;
 76   while (scanf("%d %d", &H, &A) != EOF && H != 0) {
 77     static pair<int,int> humans[250], aliens[250];
 78     for (int i = 0; i < H; i++) {
 79       scanf("%d %d", &humans[i].first, &humans[i].second);
 80     }
 81     for (int i = 0; i < A; i++) {
 82       scanf("%d %d", &aliens[i].first, &aliens[i].second);
 83     }
 84 
 85     static int dist[250][250];
 86     for (int i = 0; i < H; i++) {
 87       for (int j = 0; j < A; j++) {
 88         scanf("%d", &dist[i][j]);
 89       }
 90     }
 91     int lo = 0, hi = INF;
 92     while (lo+1 < hi) {
 93       const int mid = (lo + hi)/2;
 94       if (ok(humans, H, aliens, A, dist, mid)) {
 95         hi = mid;
 96       } else {
 97         lo = mid;
 98       }
 99     }
100     if (!ok(humans, H, aliens, A, dist, lo)) {
101       lo = hi;
102     }
103     if (lo == INF) {
104       puts("IMPOSSIBLE");
105     } else {
106       printf("%d\n", lo);
107     }
108   }
109   return 0;
110 }
poj/3343.cc