SRM696D1Med Clicounting
難しい
問題概要(原文)
$N(1 \leq N \leq 38)$ 頂点のグラフが与えられる． このうち $K (0 \leq K \leq 10)$ 本の辺はあるかどうかがわからない．
$2^K$ 通りの全ての場合における，最大クリークのサイズを求め，その和を求めよ
考察
全ての頂点は青く塗られていると考える． 生えているかどうか分からない辺の両端の頂点を赤く塗る． $K \leq 10$ より赤く塗られた頂点は最大でも $20$ 個しかない．
その後，赤く塗られた頂点が $\frac{N}{2}$ より少ない間，青色の頂点をどれか $1$ つ適当に選んで赤く塗るのを繰り返す．
赤く塗られた頂点集合を $V_1$，青く塗られた頂点集合を $V_2$ とする． $|V_1|, |V_2| \leq 20$ となる． $V_1$ だけでの最大クリークと， $V_2$ だけでの最大クリークはどちらも $2^{|V|} poly(|V|)$ ぐらいで求められることを利用する．
ここで，動的計画法を用いる． $dp_2(s_1) =$ $V_1$ の部分集合 $s_1$ について以下を満たす $V_2$ の部分集合 $s_2$ のサイズの最大値とする
- $s_2$ の誘導部分グラフはクリークをなす
- $s_1$ に含まれる任意の頂点 $u$ と，$s_2$ に含まれる任意の頂点 $v$ が隣接する，
$2^{|V_2|} poly(N)$ で $V_2$ の部分集合 $s_2$ を列挙し，以下のことをする．
- $s_2$ がクリークをなすか判定する
- $s_2$ がクリークならば， $s_2$ に含まれるどの頂点とも隣接している $V_1$ の極大部分集合 $s$ を求めて $dp_2(s)$ を埋める．
その後極大集合から部分集合に配ることで $dp_2$ の表を全て埋めることができる．
また，$dp_1(t_1) = $ $t_1$ で表される未確定の辺の部分集合辺を使うときの最大クリークのサイズ，とする．
$2^{|V_1|} poly(N)$ で $V_1$ の部分集合 $s_1$ を列挙し，以下のことをする．
- $s_1$ がクリークをなすことが可能か判定する
- $s_1$ がクリークをなすことが可能ならば，そのときの最大クリークのサイズは $|s_1| + dp_2(s_1)$ である．
- $s_1$ をクリークにするために使った未確定の辺の集合を $t$ として， $dp_1(t)$ を埋める．
その後，小さい集合から大きい集合へ配ることで $dp_1$ の表を全て埋めることができる．
計算量は $2^{\frac{N}{2}} poly(N)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class Clicounting
{
public int count(string[] gg)
{
var s1 = new HashSet<int>();
var n = gg.Length;
var g = Enumerate(n, x => new int[n]);
var k = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
if (gg[i][j] == '1') g[i][j] = g[j][i] = 100000;
else if (gg[i][j] == '0') g[i][j] = g[j][i] = -1;
else
{
g[i][j] = g[j][i] = k++;
s1.Add(i); s1.Add(j);
}
}
var s2 = new List<int>();
for (int i = 0; i < n; i++)
{
if (s1.Contains(i)) continue;
else if (s1.Count * 2 < n) s1.Add(i);
else s2.Add(i);
}
return f(s1.OrderBy(x => x).ToArray(), s2.ToArray(), g, k);
}
int f(int[] s1, int[] s2, int[][] g, int k)
{
var n = s1.Length;
var dp2 = new int[1 << n];
for (int mask = 0; mask < 1 << s2.Length; mask++)
{
var ok = true;
var cnt = 0;
var f = new bool[n];
for (int i = 0; i < n; i++)
f[i] = true;
for (int i = 0; i < s2.Length; i++)
{
if ((mask >> i & 1) == 0) continue;
cnt++;
for (int j = i + 1; j < s2.Length; j++)
{
if ((mask >> j & 1) == 0) continue;
if (g[s2[i]][s2[j]] == -1) { ok = false; break; }
}
for (int j = 0; j < s1.Length; j++)
{
if (g[s2[i]][s1[j]] == -1)
f[j] = false;
}
}
if (!ok) continue;
var ff = 0;
for (int i = 0; i < n; i++)
if (f[i]) ff |= 1 << i;
dp2[ff] = Math.Max(dp2[ff], cnt);
}
for (int i = (1 << n) - 1; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
dp2[i] = Math.Max(dp2[i | (1 << j)], dp2[i]);
}
}
Debug.WriteLine(dp2.AsJoinedString());
var dp1 = new int[1 << k];
for (int mask = 0; mask < 1 << n; mask++)
{
var ok = true;
var cnt = 0;
var f = 0;
for (int i = 0; i < n; i++)
{
if ((mask >> i & 1) == 0) continue;
cnt++;
for (int j = i + 1; j < n; j++)
{
if ((mask >> j & 1) == 0) continue;
if (g[s1[i]][s1[j]] == -1) { ok = false; break; }
else if (g[s1[i]][s1[j]] != 100000) f |= 1 << g[s1[i]][s1[j]];
}
}
if (!ok) continue;
dp1[f] = Math.Max(dp1[f], cnt + dp2[mask]);
}
for (int i = 0; i < 1 << k; i++)
{
for (int j = 0; j < k; j++)
dp1[i | (1 << j)] = Math.Max(dp1[i | (1 << j)], dp1[i]);
}
Debug.WriteLine(dp1.AsJoinedString());
return dp1.Sum();
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
static public class EnumerableEX
{
static public string AsString(this IEnumerable<char> e) { return new string(e.ToArray()); }
static public string AsJoinedString<T>(this IEnumerable<T> e, string s = " ") { return string.Join(s, e); }
}
コメント
- 半分全列挙で最大クリークを扱うテク(http://codeforces.com/blog/entry/4623?#comment-93653/) は役に立ちそう
