AOJ 2403 The Enemy of My Enemy is My Friend

問題

The Enemy of My Enemy is My Friend | Aizu Online Judge

解法

半分全列挙しました。

まず, N 頂点を半分ずつに分けて, dp[s] = (集合 s だけを使う場合の軍事力の最大値) を計算します。

で, これらを合わせるときは, 前半の頂点と隣り合っていない頂点だけを後半の頂点から選んできて, それの dp を見れば良いです。

const int MAXN = 50;
// input そのまま
string A[MAXN], D[MAXN][MAXN];
int B[MAXN], C[MAXN];
int N;

// まとめなおす情報
int strength[MAXN];
bool G[MAXN][MAXN];

ll memo[MAXN];
int dp1[1<<21], dp2[1<<21];

// s はまだ使える国として残っている際の軍事力の最大値
int dfs1(int s) {
	int& ret = dp1[s];
	if (ret >= 0) return ret;
	ret = 0;
	int n = N/2;
	for (int i = 0; i < n; i++) {
		if ((s>>i)&1) {
			// i を使ってみる
			int tmp = strength[i];
			int ns = (int)(((ll)s)&memo[i]);
			tmp += dfs1(ns);
			ret = max(ret, tmp);
		}
	}
	return ret;
}

int dfs2(int s) {
	int& ret = dp2[s];
	if (ret >= 0) return ret;
	ret = 0;
	int n = N/2, n1 = N-n;
	for (int i = 0; i < n1; i++) {
		if ((s>>i)&1) {
			// i を使ってみる
			int tmp = strength[i+n];
			int ns = (int)((ll)s & (memo[i+n]>>n));
			tmp += dfs2(ns);
			ret = max(ret, tmp);
		}
	}
	return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N) {
    	if (N==0) break;
    	map<string, int> mp;
    	for (int i = 0; i < N; i++) {
    		cin >> A[i] >> B[i] >> C[i];
    		mp[A[i]] = 0;
    		for (int j = 0; j < C[i]; j++) {
    			cin >> D[i][j];
    		}
    	}
    	{
    		int k = 0;
    		for (auto& p : mp) 
    			p.second = k++;
    	}
    	// 情報をまとめなおします
    	for (int i = 0; i < N; i++) 
    		strength[mp[A[i]]] = B[i];
    	// グラフを作ろう
    	memset(G, false, sizeof(G));
    	for (int i = 0; i < N; i++) {
    		int v = mp[A[i]];
    		G[v][v] = true;
    		for (int j = 0; j < C[i]; j++) {
    			int u = mp[D[i][j]];
    			G[v][u] = true;
    		}
    	}
    	// 計算高速化用
    	for (int i = 0; i < N; i++) {
    		ll tmp = 0;
    		for (int j = 0; j < N; j++) {
    			if (G[i][j]) tmp |= 1ll<<j;
    		}
    		tmp = ((1ll<<55)-1)^tmp;
    		memo[i] = tmp;
    	}
    	if (N==1) {
    		cout << strength[0] << endl;
    		continue;
    	}
    	// 半分全列挙
    	memset(dp1, -1, sizeof(dp1));
    	memset(dp2, -1, sizeof(dp2));
    	int n = N/2, n1 = N-n;
    	int v = mp[A[0]];
    	int ans = 0;
    	for (int s = 0; s < 1<<n; s++) {
    		bool ng = false;
    		for (int i = 0; i < n; i++) {
    			if (G[v][i] && ((s>>i)&1)) ng = true;
    		}
    		if (v < n && ((s>>v)&1)) ng = true;
    		if (ng) continue;
    		ll flag = (1ll<<N)-1;
    		for (int i = 0; i < n; i++) {
    			if ((s>>i)&1) {
    				flag &= memo[i];
    			}
    		}
    		flag &= memo[v];
    		int ns = (int)(flag>>n);
    		ans = max(ans, strength[v]+dfs1(s)+dfs2(ns));
    	}
    	cout << ans << endl;
    }
    return 0;
}