[WorldFinal 2012E]Infiltration（dfs+图论）

Description

题意：给定一个点数为n的竞赛图，求图的最小支配集

n<=75

Solution

如果将竞赛图的一个点删去，这个图还是竞赛图

而竞赛图每个点相连的边数为(n-1)，那么删去一个点后这个图变成原图一半大小的竞赛图

由此可知竞赛图的最小支配集是log(n)级别的

那么答案最大为6，爆搜即可

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <bitset>

using namespace std;

bitset<99> g[99],tmp;

int cas,n,path[9],Ans;

bool dfs(int k,int p,bitset<99> cur){

	if(k>=Ans) return (cur.count()==n);//支配所有点

	for(int i=p;i<=n;++i)

		if(dfs(k+1,(path[k+1]=i),cur|g[i])) return 1;

	return 0;

}

int main(){

	while(~scanf("%d",&n)){

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j){

				char ch=getchar();while(ch!='0'&&ch!='1')ch=getchar();

				g[i][j]=ch-'0';

				if(i==j)g[i][j]=1;//包括自己这个点

		}

		for(Ans=1;Ans<=10;Ans++) if(dfs(0,1,tmp))break;//迭代加深搜索

		printf("Case %d: %d ",++cas,Ans);

		for(int i=1;;++i) printf("%d ",path[i]);

		printf("\n");

		for(int i=1;i<=n;++i) g[i]=tmp;//初始化

	}

	return 0;

}

巴特西

[WorldFinal 2012E]Infiltration（dfs+图论）

Description

Solution

Code

最新文章

热门文章