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

コメント