BZOJ 3632 外太空旅行 DFS

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

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

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

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

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

这样就可以过了- –

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

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 60using 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;}

我要扼住命运的咽喉。