BZOJ 3632 外太空旅行 DFS

题目大意：给定一张无向图，求最大团

从小到大依次枚举每个点加或者不加 如果加必须满足加入后是一个团

这样状态数很大显然会T 因此可以考虑加入剪枝

统计还未加入的所有点中有多少点可以加入当前的团

如果这样的点的数量加上当前团中点的数量仍然比ans小 就剪枝

这样就可以过了- -

其实根据这个估价函数还可以写个A*。。。 我懒得写了。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 60
using namespace std;
int n,ans;
long long a[M];
void DFS(int pos,long long sta,int cnt)
{
	if(pos==n+1)
	{
		ans=max(ans,cnt);
		return ;
	}
	if(cnt+(n-pos+1)<=ans)
		return ;
	if( (sta&a[pos])==sta )
		DFS(pos+1,sta|(1ll<<pos-1),cnt+1);
		
	int i,temp=0;
	for(i=pos+1;i<=n;i++)
		if( (sta&a[i])==sta )
			++temp;
	if(temp+cnt<ans)
		return ;
		
	DFS(pos+1,sta,cnt);
}
int main()
{
	int x,y;
	cin>>n;
	while(~scanf("%d%d",&x,&y) )
	{
		a[x]|=(1ll<<y-1);
		a[y]|=(1ll<<x-1);
	}
	DFS(1,0,0);
	cout<<ans<<endl;
	return 0;
}

BZOJ 3632 外太空旅行 DFS

原文：http://blog.csdn.net/popoqqq/article/details/44623165