な bit DP としてよく知られている問題ですね！
EDPC U - Grouping の類題と言える！
問題概要
頂点数 、辺数
の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラフがいずれもクリークとなるようにしたい。
分割されたグループの個数の最小値を求めよ。
制約
解法 (1)：
の bit DP
こんな bit DP をすれば OK！！！
dp[bit]← bit に対応する頂点集合をいくつかのクリークに分割するとき、分割されたクリークの個数の最小値
そして遷移は次の通り。
// 頂点集合 add が、bit と共通要素を持たず、クリークであるとする chmin(dp[bit | add], dp[bit] + 1);
これは一見すると、bit が 通りあって、そのそれぞれに対して add が
通りあって、全体で
通りに思えてしまうかもしれない。しかし実はちゃんと解析すると
となって十分間に合うのだ。具体的には
「add は、bit の補集合の部分集合しか動かない」
という点に着目する。実装上はこんな感じにできる。ここで、「部分集合の部分集合を列挙する方法」を活用している。
for (int bit = 0; bit < (1<<N); ++bit) { int cbit = (1<<N) - 1 - bit; // 補集合 for (int add = cbit; ; add = (add-1) & cbit) { if (!add) break; // 頂点集合 add がクリークかどうかを表す配列 ok を予め求めておく if (ok[add]) chmin(dp[bit|add], dp[bit] + 1); } }
この処理の計算量が であることを示そう。実は簡単だ。(bit, add) のとりうる値は次のように考えると
通りしかない。各頂点
について、
- 頂点
は頂点集合 bit に含まれる
- 頂点
- 頂点
という 3 パターンしかない。したがって、考えられる状況は 通りなのだ。以上から、今回の bit DP の計算量が
であることがわかった。
コード
前処理として、以下の配列を求めている。
ok[bit]← 頂点集合 bit がクリークかどうか
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int main() { int N, M; cin >> N >> M; vector<vector<int>> G(N, vector<int>(N, false)); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; --a, --b; G[a][b] = G[b][a] = true; } vector<bool> ok(1<<N, true); for (int bit = 0; bit < (1<<N); ++bit) { vector<int> vs; for (int i = 0; i < N; ++i) if (bit & (1<<i)) vs.push_back(i); for (int i = 0; i < vs.size() && ok[bit]; ++i) { for (int j = i+1; j < vs.size() && ok[bit]; ++j) { if (!G[vs[i]][vs[j]]) ok[bit] = false; } } } const int INF = 1<<29; vector<int> dp(1<<N, INF); dp[0] = 0; for (int bit = 0; bit < (1<<N); ++bit) { if (dp[bit] >= INF) continue; int cbit = (1<<N) - 1 - bit; for (int add = cbit; ; add = (add-1) & cbit) { if (!add) break; if (ok[add]) chmin(dp[bit|add], dp[bit] + 1); } } cout << dp[(1<<N)-1] << endl; }
解法 (2)：補グラフの彩色数
クリークといえば、補グラフをとれば「安定集合」になる。安定集合とは、
「頂点集合の部分集合であって、どの 2 頂点間にも辺がないようなもの」
のことを指す。クリークを見たら補グラフをとるのはありかもしれない。さて、もとのグラフで同一のグループの頂点は同じ色で塗り、異なるグループの頂点は異なる色で塗るとしたとき、
- もとのグラフで条件を満たしている場合、同じ色の頂点間にはすべて辺があるので、補グラフでは辺彩色 (同じ色の頂点間には辺がない) になっている
- 補グラフで辺彩色になっている場合、同じ色の頂点間にはすべて辺がないので、もとのグラフでは同じ色の頂点間にはすべて辺がある
というふうになっている。つまり、補グラフの彩色数を求めれば OK。補グラフの彩色数は次の記事で書いた。計算量は でできる！
コード
#include <bits/stdc++.h> using namespace std; // 彩色数 long long modpow(long long a, long long n, long long MOD) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % MOD; a = a * a % MOD; n >>= 1; } return res; } int chromatic_number(const vector<vector<int> > &G) { const int MOD = 1000000007; int n = (int)G.size(); vector<int> neighbor(n, 0); for (int i = 0; i < n; ++i) { int S = (1<<i); for (int j = 0; j < n; ++j) if (G[i][j]) S |= (1<<j); neighbor[i] = S; } // I[S] := #. of inndepndet subset of S vector<int> I(1<<n); I[0] = 1; for (int S = 1; S < (1<<n); ++S) { int v = __builtin_ctz(S); I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]]; } int low = 0, high = n; while (high - low > 1) { int mid = (low + high) >> 1; // g[S] := #. of "k independent sets" which cover S just // f[S] := #. of "k independent sets" which consist of subseta of S // then // f[S] = sum_{T in S} g(T) // g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T] long long g = 0; for (int S = 0; S < (1<<n); ++S) { if ((n - __builtin_popcount(S)) & 1) g -= modpow(I[S], mid, MOD); else g += modpow(I[S], mid, MOD); g = (g % MOD + MOD) % MOD; } if (g != 0) high = mid; else low = mid; } return high; } int main() { int N, M; cin >> N >> M; vector<vector<int>> G(N, vector<int>(N, 1)); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; --a, --b; G[a][b] = G[b][a] = 0; } cout << chromatic_number(G) << endl; }
