AOJ2011

Gather the Maps!

■問題
n人の子孫がそれぞれ宝の地図の断片を１枚ずつ持っています。
n人の日程はわかり、その日が暇な人同士なら誰かにその断片を渡すことができます。
誰かがすべての断片を手にするまでの最小の日数を求めなさい。

■解法
誰かの断片を別の誰かに渡す時、当然だが持っているすべてを渡すほうが良い。
さらに、渡すという処理は自分のものを渡すのではなくそのコピーを渡してやるというふうに処理するとスケジュールがあった場合の渡した場合と渡さなかった場合の両方の状態を調べることができる。
誰がどの断片を持っているかはbitを使って管理して、渡す処理はORを取ればいいためすべてのbitが立つ状態になるまでシミュレーションすればよい。
また、人数はn<=50なのでbitで管理する変数は2^50が入るlong long intで無くてはならない。
プログラム中のシフト演算でもオーバーフローに気をつける。

■ソース

#include <cstdio>
#include <vector>
using namespace std;
int main(void){
  while(1){
    long long int c[55];
    vector<int> d[33];
    int n;
    scanf("%d",&n); if(!n) break;
    for(int i = 0; i < n; i++){
      c[i] = 1LL << i;
      int f;
      scanf("%d",&f);
      for(int j = 0; j < f; j++){
	int a;
	scanf("%d",&a);
	d[a].push_back(i);
      }
    }
    bool f = false;
    for(int i = 1; i <= 30; i++){
      for(int j = 0; j < (int)d[i].size(); j++){
	for(int k = 0; k < (int)d[i].size(); k++){
	  c[d[i][k]] |= c[d[i][j]];
	  if(c[d[i][k]] == (1LL << n) - 1){
	    f = true;
	    printf("%d\n",i);
	    break;
	  }
	}
	if(f) break;
      }
      if(f) break;
    } 
    if(!f) puts("-1");
  }
}