TopCoder SRM 571 Div1 Medium MagicMolecule

問題

n頂点からなる無向グラフが与えられる。
頂点には重みa[i]がついている。


このグラフの大きさ2*n/3以上のクリークで、
重みの和が最大になるものにおける、重みの和を求めよ。


クリークが存在しないとき、-1を返せ。

制約条件

n≦50
a[i]≦100000

方針

クリークは補グラフにおける独立集合になる。
独立集合の補集合は頂点被覆になる。
したがって、補グラフにおける、サイズn/3以下の重み最小の頂点被覆を求めればよい。


証明:
ある頂点被覆をVC, その補集合をG-VCとあらわす。
任意の頂点u, v∈G-VCを取る。
u, v間に辺があるとすると、u, vのどちらかが頂点被覆に属することになり矛盾、
したがってG-VCは独立集合


独立集合をIとする
任意の辺e(u, v)∈Eを取る。
独立集合の定義より、両方がIに属することはない。
すなわち、どちらかがG-Iに属する。
これはG-Iが頂点被覆であることに他ならない。


サイズkの頂点被覆はO(2^k poly(n))で求まる。
なぜなら、頂点iを使わないと決めると、辺のもう一方の頂点は必ず使うため、
頂点iを使うと決めても明らかに、
どちらも場合も残りの頂点数は1以上減る。


2通りの分岐が、最大で深さk回起こるのだから、計算量はO(2^k poly(n))で抑えられる。
これを再帰を使って適当に実装すればよい。

ソースコード

int n, a[50], ans;
bool e[50][50];

void rec(int c, ll bit, int sum){
	if(3 * __builtin_popcountll(bit) > n || sum >= ans) return;
	if(c == n){
		ans = min(ans, sum);
		return;
	}
	
	bool ok = 0;
	rep(i, n) if(e[c][i]) ok = 1;
	//孤立点の場合は使わなくてよい
	if(!ok){
		rec(c + 1, bit, sum);
		return;
	}
	//隣接する頂点のうち、前につながっていたもので置き忘れたのがあったら、ここに置く
	if(bit >> c & 1){
		rec(c + 1, bit | 1ll << c, sum);
		return;
	}
	
	ok = 1;
	rep(i, c) if(e[c][i] && !(bit >> i & 1)) ok = 0;
	//前の頂点に置忘れがない場合、ここに置かなくてもいい。
	if(ok){
		ll nbit = bit;
		int nsum = sum;
		rep(i, n) if(!(bit >> i & 1) && e[c][i]){
			nsum += a[i];
			nbit |= 1ll << i;
		}
		rec(c + 1, nbit, nsum);
	}
	//未来におく必要のあるものがない場合、ここには置かなくてよい。
	//これがないとTLE.
	ok = 1;
	for(int i = c + 1; i < n; i++) if(e[c][i] && !(bit >> i & 1)) ok = 0;
	if(!ok) rec(c + 1, bit | 1ll << c, sum + a[c]);
}

class MagicMolecule {
	public:
	int maxMagicPower(vector <int> magicPower, vector <string> magicBond) {
		n = magicPower.size();
		rep(i, n) a[i] = magicPower[i];
		rep(i, n) rep(j, n) if(i != j) e[i][j] = magicBond[i][j] == 'N';
		ans = inf;
		int s = 0;
		rep(i, n) s += a[i];
		rec(0, 0, 0);
		return ans == inf ? -1 : s - ans;
	}
};