問題
https://community.topcoder.com/stat?c=problem_statement&pm=14340
n頂点の単純無向グラフがある。
この単純無向グラフの辺のうち、k個の辺が有るかどうか分からない。
この辺の有無によって、2^k通りのグラフの組合せがある。
その全ての組合せについて、最大クリーク問題を解き、その答えの総和を答えよ。
1 <= n <= 38
0 <= k <= 10
帰納的考察(antaさんのツイート見てググった)
1. 38とかまたbitDP???
2. 終わり
――壁――
3. 今回の問題は「全ての組合せについて最大クリーク問題を解く」ことをそのままやるだけ
4. このライブラリをどこからか持ってきて解きました
5. 最大クリークライブラリの確認にはABC002のD問題も使えます
http://abc002.contest.atcoder.jp/tasks/abc002_4
実装
// https://github.com/tzupengwang/PECaveros/blob/master/codebook/graph/MaxClique.cpp class MaxClique { public: static const int MV = 210; int V, ans; int el[MV][MV / 30 + 1]; int dp[MV]; int s[MV][MV / 30 + 1]; vector<int> sol; void init(int v) { V = v; ans = 0; memset(el, 0, sizeof(int) * MV * (MV / 30 + 1)); memset(dp, 0, sizeof(int) * MV); } /* Zero Base */ void addEdge(int u, int v) { if (u > v) swap(u, v); if (u == v) return; el[u][v / 32] |= (1 << (v % 32)); } bool dfs(int v, int k) { int c = 0, d = 0; for (int i = 0; i<(V + 31) / 32; i++) { s[k][i] = el[v][i]; if (k != 1) s[k][i] &= s[k - 1][i]; c += __builtin_popcount(s[k][i]); } if (c == 0) { if (k > ans) { ans = k; sol.clear(); sol.push_back(v); return 1; } return 0; } for (int i = 0; i<(V + 31) / 32; i++) { for (int a = s[k][i]; a; d++) { if (k + (c - d) <= ans) return 0; int lb = a&(-a), lg = 0; a ^= lb; while (lb != 1) { lb = (unsigned int)(lb) >> 1; lg++; } int u = i * 32 + lg; if (k + dp[u] <= ans) return 0; if (dfs(u, k + 1)) { sol.push_back(v); return 1; } } } return 0; } int solve() { for (int i = V - 1; i >= 0; i--) { dfs(i, 1); dp[i] = ans; } return ans; } }; //----------------------------------------------------------------- struct Clicounting { int count(vector<string> g) { int n = g.size(); vector<int> undef; rep(i, 0, n) rep(j, i + 1, n) if (g[i][j] == '?') undef.push_back(i * 100 + j); int nn = undef.size(); int ans = 0; rep(m, 0, 1 << nn) { MaxClique mc; mc.init(n); rep(i, 0, n) rep(j, 0, n) if (g[i][j] == '1') mc.addEdge(i, j); rep(i, 0, nn) if (m & (1 << i)) { int ii = undef[i] / 100; int jj = undef[i] % 100; mc.addEdge(ii, jj); } ans += mc.solve(); } return ans; } };