AOJ 2011 - Gather the Maps!

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011

概要

n 人がそれぞれ地図の一部を持っていて，1対1で会って自分の持っている地図を渡していって最終的に一箇所に集めたい． それぞれの人の空いている日付のリストが与えられるので，最短で何日に一箇所に集められるかを答える．予定が空いているなら一人が一日に何人と会ってもよい．

30日以内に全て集められないときは -1 を出力する．

制約

解法

i の人が d 日目までに持てる地図の組み合わせを DP 的に更新しながら，最初に誰かが全部持てたときの d を答える．

n <= 50 なので，地図の組み合わせは long long のビットで表現すると楽． 

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (cin >> N && N != 0) {
 9     vector<vector<int> > v(N, vector<int>(31, 0));
10     for (int i = 0; i < N; i++) {
11       int n;
12       cin >> n;
13       for (int j = 0; j < n; j++) {
14         int x;
15         cin >> x;
16         v[i][x] = 1;
17       }
18     }
19 
20     vector<unsigned long long> w(N, 0);
21     for (int i = 0; i < N; i++) {
22       w[i] = 1ULL<<i;
23     }
24 
25     for (int d = 1; d <= 30; d++) {
26       vector<int> us(N, 0);
27       unsigned long long s = 0ULL;
28       for (int i = 0; i < N; i++) {
29         for (int j = i+1; j < N; j++) {
30           if (v[i][d] && v[j][d]) {
31             us[i] = us[j] = 1;
32             s |= w[i] | w[j];
33           }
34         }
35       }
36       if (s == (1ULL<<N)-1) {
37         cout << d << endl;
38         goto NEXT;
39       }
40       for (int i = 0; i < N; i++) {
41         if (us[i]) {
42           w[i] = s;
43         }
44       }
45     }
46     cout << -1 << endl;
47 NEXT:
48     ;
49   }
50 }
aoj/2011.cc