AOJ2061 International Party

問題リンク International Party

• 概要

N個の言語が飛び交うパーティーがあり、M個のグループがある。i番目のグループはki個の言語だけ使うことができる。パーティー全体で使用できる言語を最も小さくし、なおかつ任意の2グループ間でおしゃべりができるような言語の集合を答えよ。そのような集合が無かったり、必要最小数が5を超える場合は"Impossible"と答えよ。
1 <= N <= 30
2 <= M <= 20
1 <= ki <= 20

• 解法

全探索です。
使用を許す言語の組み合わせを全て試します。総数は 30C1 + 30C2 + 30C3 + 30C4 + 30C5 < 200000 程度です。
M個のグループを頂点とするグラフを作り、使うことを許された言語のみを使って、全頂点を連結できるかを深さ優先などで試します。
※グループiとjが i-k, k-jと繋がっているとき、グループkを翻訳係として、iとjはおしゃべりすることができます

• ソース

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//International Party
public class AOJ2061 {

	int n, m, INF = 1<<29, min;
	boolean[] u, v, res;
	boolean[][] e;
	
	int dfs(int k){
		if(v[k])return 0;
		int res = 1;
		v[k] = true;
		for(int i=0;i<n;i++){
			if(!u[i]||!e[k][i])continue;
			for(int j=0;j<m;j++)if(e[j][i])res += dfs(j);
		}
		return res;
	}
	
	void f(int k, int d){
		if(5<d||min<=d)return;
		v = new boolean[m];
		if(dfs(0)==m){
			min = d;
			res = u.clone(); return;
		}
		for(int i=k;i<n;i++){
			u[i] = true;
			f(i+1, d+1);
			u[i] = false;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(boolean h = true;;h=false){
			n = sc.nextInt(); m = sc.nextInt();
			if((n|m)==0)break;
			if(!h)System.out.println();
			Map<String, Integer> ref = new HashMap<String, Integer>();
			String[] s = new String[n];
			for(int i=0;i<n;i++){
				s[i] = sc.next();
				ref.put(s[i], i);
			}
			e = new boolean[m][n];
			for(int i=0;i<m;i++){
				int k = sc.nextInt();
				while(k--!=0)e[i][ref.get(sc.next())] = true;
			}
			u = new boolean[n];
			min = INF;
			f(0, 0);
			if(min==INF)System.out.println("Impossible");
			else {
				System.out.println(min);
				for(int i=0;i<n;i++)if(res[i])System.out.println(s[i]);
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ2061().run();
	}
}