AOJ2403 The Enemy of My Enemy is My Friend

問題リンク The Enemy of My Enemy is My Friend

• 解法

探索+枝刈りで解きました。
まず、国に番号付けをします。自国が0なら他の国はどんな番号でもいいです。
次に、i番の国に隣接している国をビットマスクの形で保持します。これをadj[i]とします。
更に
sum[k]: k〜N-1番の国の軍事的強さの総和
これを準備したら、1からN-1まで順番に再帰で、同盟国にするかしないかを決めます。
同盟国に隣接している国をビットマスクとしてmaskで管理します。
maskのk番目のビットが立っていたらその国は同盟国にできないとわかります
k番目のビットが立っていなかったら、採用する場合としない場合で再帰します。
また、k番目の国について再帰で潜っている時、それ以降で得られる強さは最大sum[k]です。よって
現在の軍事的強さ + sum[k] <= 現在の解
なら解の更新が見込めないので枝刈りします。
これで解けました。

• ソース

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

//The Enemy of My Enemy is My Friend
public class AOJ2403 {

	Map<String, Integer> ref;
	int ID;
	int reg(String s){
		if(ref.containsKey(s))return ref.get(s);
		ref.put(s, ID);
		return ID++;
	}
	
	int N, res;
	int[] sum, B;
	long[] adj;
	
	void f(int k, int score, long mask){
		res = Math.max(res, score);
		if(k==N)return;
		if(score+sum[k]<=res)return;
		if(((mask>>k)&1)==0)f(k+1, score+B[k], mask|adj[k]);
		f(k+1, score, mask);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			N = sc.nextInt();
			if(N==0)break;
			ref = new HashMap<String, Integer>();
			ID = 0;
			adj = new long[N];
			B = new int[N];
			for(int i=0;i<N;i++){
				int id = reg(sc.next());
				B[id] = sc.nextInt();
				int m = sc.nextInt();
				while(m--!=0)adj[id]+=1L<<reg(sc.next());
			}
			sum = new int[N+1];
			for(int i=N-1;i>=0;i--)sum[i]=sum[i+1]+B[i];
			res = 0;
			f(1, B[0], adj[0]);
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new AOJ2403().run();
	}
}