AtCoder ABC #187 : F - Close Group

今年からはABCはF問題だけ書いてきます。そのうちF問題も書くのやめるかも。
https://atcoder.jp/contests/abc187/tasks/abc187_f

問題

N頂点の単純無向グラフが与えられる。
このグラフからいくつか辺を取り除き、連結成分内の頂点間はすべて辺があるようにしたい。
元のグラフは、最小何個の条件を満たす連結成分から構成可能か。

解法

最小いくつの完全グラフに分解できるかという問題となる。
Nは小さいので、まずある頂点集合が完全グラフを構築できるかを求めよう。
すなわち以下を求める。
f(x) := xに示す頂点集合とその誘導グラフが完全グラフを成すなら1、そうでないなら∞
各頂点における隣接辺をbitmapで持つようにすると、f(x)はBitDPの要領でO(N*2^N)で埋められる。

g(x) := xに示す頂点集合は、最小いくつの完全グラフに分割できるか
とする。g(全頂点の集合)が求める解である。
g(x) = min( f(x), g(y)+g(x\y))
なので、集合の部分集合を列挙するテクを用いるとこちらはO(3^N)で処理できる。

合わせるとO(N*2^N + 3^N)で求めることができる。

int N,M;
int E[18];
int P[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x]|=1<<y;
		E[y]|=1<<x;
	}
	FOR(i,N) E[i]|=1<<i;
	
	int mask;
	FOR(mask,1<<N) {
		P[mask]=__builtin_popcount(mask);
		
		FOR(i,N) if(mask&(1<<i)) {
			if((E[i]&mask)==mask && P[mask^(1<<i)]==1) P[mask]=1;
			break;
		}
		for(int sm=mask; sm>0; sm=(sm-1)&mask) {
			P[mask]=min(P[mask],P[sm]+P[mask^sm]);
		}
	}
	cout<<P[(1<<N)-1]<<endl;
	
}

まとめ

むしろ問題文を理解するのに手間取った。