AOJ-2011 : Gather the Maps!

Gather the Maps! | Aizu Online Judge

それぞれが持っている地図の一部を集めて、地図を完成させたい。地図は手渡しで一人に集める方式を取ります。それぞれの空いている日にちが与えられるので、それを元に最短何日で地図を完成させられるか。期間内に集める事が出来ない場合は"-1"を出力する。

誰の地図が集まっているかは、ビットを使って表現します。N人の場合は、Nビット用意して、3番目の人の地図が手に入れば、3番目のビットを立てるという感じです。

求めるのは最短日数なので、誰の手元に集めたかという風にするのではなく、全員に渡したとして計算していきます。1番目と3番目の人が集まった場合は、両方に1番目と3番目の地図を渡します。

dp[N][MAX]; //i番目の人がj日目までに集められる最大値(bitで表現)

のように定義して、それぞれの空いている日にちの配列を使って計算します。
空いている日の場合は、他の空いている日にちの人の地図を全て受け取ります。その他の場合は、自分の地図だけを受け取ります。

また、1≦N≦50まであるため、50桁ビットを用意するとint型の範囲を超えるので、long long型にしています。

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

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

const int MAX = 31;

typedef long long ll;

int main()
{
	int N,M;
	while( cin >> N && N )
	{
		ll dp[N][MAX]; //i番目の人がj日目までに集められる最大値(bitで表現)
		bool is_ok[N][MAX]; //その人の都合を表す配列
		fill_n((int *)dp, sizeof(dp) / sizeof(int), 0);
		fill_n((bool *)is_ok, sizeof(is_ok) / sizeof(bool), false);

		int f;
		rep(i,N)
		{
			cin >> M;
			rep(m,M){
				cin >> f;
				is_ok[i][f] = true;
			}	
		}
		
		REP( i, 0, N ){
			dp[i][0] |= 1LL<<i;
		}

		const ll COMP = (1LL<<N)-1;
		int ans=-1;
		REP( j, 1, MAX ){
			REP( i, 0, N ){
				if(is_ok[i][j]){
					REP( k, 0, N ){
						if(is_ok[k][j]){
							dp[i][j] |= dp[k][j-1];
						}
					}
				}else{
					dp[i][j] |= dp[i][j-1];
				}
	
				if(dp[i][j] == COMP){ ans=j; goto end; }
			}
		}
end:
		cout << ( (ans==-1) ? -1 : ans ) << endl;  
	}
	return 0;
}