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; } };