AtCoder Beginner Contest 187, F : Close Group

問題文

　https://atcoder.jp/contests/abc187/tasks/abc187_f

問題概要

　$N$ 頂点 $M $ 辺の単純無向グラフ $G = ( V, E )$ がある．このグラフをクリークで被覆するときの最小のクリーク数を求めよ*1．

制約

• $1 \leq N \leq 18$
• $0 \leq M \leq \frac{ N ( N - 1 ) } 2$

解法

　頂点集合からクリークを一つずつ取り除いていくことを考えると，次のように状態をとる動的計画法を考えることができます．

• $dp_s :=$ 頂点集合 $s$ を被覆できるクリーク被覆の最小のクリーク数

$dp_s$ からの遷移では，次のクリークとして取り出す頂点集合 $t$ をすべて試して，2 条件

• $t$ がクリークをなす
• $s \setminus t = \emptyset$

を満たすときに $dp_{ s \cup t }$ を $\min( dp_{ s \cup t }, dp_s + 1 )$ で更新します．更新が終わった後，$dp_V$ を読むと答えが求まっています．

コード

constexpr auto INF = LIM< int >::max() / 2;

int main()
{
	IN( int, N, M );
	VVI G( N, VI( N ) );
	REP( M )
	{
		IN( int, u, v );
		--u, --v;
		G[u][v] = G[v][u] = 1;
	}

	VI is_clique( 1 << N );
	REP( s, 1 << N )
	{
		bool ok = true;
		REP( i, N )
		{
			REP( j, i )
			{
				if ( !( s & 1 << i ) || !( s & 1 << j ) )
				{
					continue;
				}
				ok &= G[i][j];
			}
		}

		is_clique[s] = ok;
	}
	
	static int dp[ 1 << 18 ];
	fill( AALL( dp ), INF );
	dp[0] = 0;
	REP( s, 1 << N )
	{
		const int s_ = ( ( 1 << N ) - 1 ) & ~s;

		for ( int t = ( 1 << N ) - 1; 0 <= t; --t )
		{
			t &= s_;
			if ( is_clique[t] )
			{
				chmin( dp[ s | t ], dp[s] + 1 );
			}
		}
	}
	cout << dp[ ( 1 << N ) - 1 ] << endl;

	return 0;
}

*1:原文と変わっていますが，結局，連結成分内の任意の 2 頂点が連結ならばその連結成分は元のグラフのクリークということになります