AOJ2011 Gather the Maps!

問題リンク Gather the Maps!

• 解法

DPです。
dp[i][j]: i番目の人の手にj日目までに集めることができる地図の最大の集合
とします。地図には0〜n-1番号がついているものとし、集合はその番号の桁のbitを立てることで、整数で表すものとします。
dp[i][j]の漸化式は次の通りです。
i番目の人のj日目の都合が悪い場合、dp[i][j]はそのままでdp[i][j-1]です。
都合がつく場合、j日目に都合がいいその他の人kの持っている地図をマージしたものがi番目の手元に渡ります。即ち、
dp[i][j] = dp[i][j] | dp[k][j-1] (k=0, 1, 2...)
dp[i][j]が(2^n)-1と同じ(全ての地図が集まった)ならばそのjが答えです。

• ソース

import java.util.Scanner;

//Gather the Maps!
public class AOJ2011 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			boolean[][] f = new boolean[n][31];
			for(int i=0;i<n;i++){
				int k = sc.nextInt();
				while(k--!=0)f[i][sc.nextInt()] = true;
			}
			long[][] dp = new long[n][31];
			for(int i=0;i<n;i++)dp[i][0] = 1L << i;
			int res = -1;
			for(int j=1;j<=30;j++){
				if(res!=-1)break;
				for(int i=0;i<n;i++){
					if(!f[i][j]){
						dp[i][j] = dp[i][j-1]; continue;
					}
					for(int k=0;k<n;k++){
						if(!f[k][j])continue;
						dp[i][j]|=dp[k][j-1];
					}
					if(dp[i][j]==(1L<<n)-1){
						res = j; break;
					}
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2011().run();
	}
}