Problem 1015 : Dominating Set

問題概要

重みのない無向グラフで表される都市が与えられる。
グラフの頂点の場所にいくつかスーパーを出店し、どの頂点に住む人も、その頂点または隣の頂点にスーパーがあるような状態にしたい。

このとき、必要なスーパーの数の最小値を求めよ。

解法

グラフのサイズが書いてないが、頂点数≦100として問題なく通った。
これは一般グラフの最小点カバー問題（＝最大独立集合に帰着可能）で、NP困難な問題である。

したがって、効率のよいアルゴリズムはないと考えられるので、ここでは枝刈り探索をしてみた。
深さ優先探索で頂点を一つずつ、出店するか出店しないかを決めていき、「その時点でカバーできない辺が出てきてしまっ」たら枝刈り、また、「出店の数が既にわかっている最大値を超えてしまっ」ても枝刈り、としたら0.02sで通った。

ソースコード

int n,m,ans;
vector<vi> e;
bool u[100];

void rec(int c,int use)
{
	if(use>=ans)return;
	
	int p=0;
	for(;p<n;p++)//周りに店がないか調べる
	{
		if(u[p])continue;
		bool cand=0;
		fr(i,e[p])
		{
			if(u[*i])goto NEXT;
			if(*i>=c)cand=1;
		}
		if(!cand)return; else break;
		NEXT:;
	}
	if(p==n)//自分または隣に店のない頂点はない
	{
		ans=min(ans,use); return;
	}
	if(c>=n)return;
	
	rec(c+1,use);
	u[c]=1; rec(c+1,use+1); u[c]=0;
}
int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		e.clear(); e.resize(n);
		rep(i,n)u[i]=0;
		
		rep(i,m)
		{
			int x,y; scanf("%d%d",&x,&y);
			e[x].pb(y); e[y].pb(x);
		}
		ans=n; rec(0,0);
		printf("%d\n",ans);
	}
	return 0;
}