無向グラフについて、頂点を共有しない完全部分グラフの最小個数を求める。
解説
頂点からなる集合$S$の完全部分グラフの最小個数を$dp[S]$とする。$dp[\phi]=0$で、$S$が完全グラフをなすならば$dp[S]=1$である。それ以外の場合、 $$ dp[S]=\min \{ dp[T] + dp[S\setminus T] \mid T \subset S \} $$ となる。
実装
グラフは隣接行列で管理した。
$\{0,\ldots, n - 1 \}$の部分集合$S$に対して、$S$の空でない部分集合を列挙するには次のようにすればよい。例えば、$S=\{0,1,3\}$の場合、$11 = 2 ^ 0 + 2 ^ 1 + 2 ^ 3$だから
s = 11 t = s while t: print(t) t = (t - 1) & s # 11, 10, 9, 8, 3, 2, 1
Submission #19170982 - AtCoder Beginner Contest 187
n, m = map(int, input().split()) graph = [[0] * n for _ in range(n)] for _ in range(m): a, b = map(int, input().split()) graph[a - 1][b - 1] = 1 graph[b - 1][a - 1] = 1 dp = [n] * (1 << n) dp[0] = 0 bit_count = [bin(s).count("1") for s in range(1 << n)] for s in range(1, 1 << n): # 1点の場合 if bit_count[s] == 1: dp[s] = 1 continue # 完全部分グラフの場合 comp = True for i in range(n - 1): if not (1 << i) & s: continue for j in range(i + 1, n): if not (1 << j) & s: continue if not graph[i][j]: comp = False break if comp: dp[s] = 1 continue # その他 t = s while t: t = (t - 1) & s dp[s] = min(dp[s], dp[t] + dp[s - t]) print(dp[(1 << n) - 1])
ちなみに、隣接行列ではなく各頂点に隣接する点の集合を管理するようにすると、完全部分グラフ判定がかんたんに書ける。
Submission #19171171 - AtCoder Beginner Contest 187
n, m = map(int, input().split()) graph = [1 << i for i in range(n)] for _ in range(m): a, b = map(int, input().split()) graph[a - 1] |= 1 << (b - 1) graph[b - 1] |= 1 << (a - 1) dp = [n] * (1 << n) dp[0] = 0 for s in range(1, 1 << n): # 完全部分グラフの場合 if all((s & graph[i]) == s for i in range(n) if (1 << i) & s): dp[s] = 1 continue # その他 t = s while t: t = (t - 1) & s dp[s] = min(dp[s], dp[t] + dp[s - t]) print(dp[(1 << n) - 1])
