Clicounting [SRM 696 : Div1 Mid]

問題

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