ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2011 Gather the Maps!

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011


・概要一人一枚ずつ持っている地図の断片をひとつに集める問題です。
問題文が日本語なので省略


・解法
DPで解くことができます。
(最初はUnion find treeか?などと考えたり…)

まず誰が何日にあいているかというのを、table[31][51]に保存しました。
table[何日][誰か]に空いているか? true : false

そしてDPには、DP[何日に][誰が][誰の]地図の破片を持っている可能性があるか? true : false を持たせます。

各日にちで誰かがみんなの地図の破片を持っている可能性があればそこで打ち切り、それが解となります。 30日経っても全員分揃わない場合はー1を出力となります。


ソースコード

#include<iostream>
#include<cstring>
using namespace std;

int n;
bool table[31][51], dp[31][51][51];

int solve(){
   for(int i = 1 ; i <= n ; i++)dp[0][i][i] = true;

   for(int day = 1 ; day <= 30 ; day++){
      for(int i = 1 ; i <= n ; i++){
	 for(int j = 1 ; j <= n ; j++){
	    if((table[day][i] && table[day][j]) || i==j){
	       for(int k = 1 ; k <= n ; k++){
		  dp[day][i][k] |= (dp[day-1][i][k] | dp[day-1][j][k]);
		  dp[day][j][k] |= (dp[day-1][i][k] | dp[day-1][j][k]);
	       }
	    }
	 }
      }
      
      for(int i = 1 ; i <= n ; i++){
	 bool check = true;
	 for(int j = 1 ; j <= n ; j++){
	    if(!dp[day][i][j]){
	       check = false;
	       break;
	    }
	 }
	 if(check)return day;
      }
   }
   return -1;
}

int main(){
   while(cin >> n){
      if(n==0)break;
      
      memset(table,false,sizeof(table));
      memset(dp,false,sizeof(dp));
     
      for(int i = 1 ; i <= n ; i++){
	 int f;
	 cin >> f;
	 for(int j = 0 ; j < f ; j++){
	    int tmp;
	    cin >> tmp;
	    table[tmp][i] = true;
	 }
      }

      cout << solve() << endl;
   }  
   return 0;
}