题解 P1692 【部落卫队】
sukimo
2020-06-06 18:27:20
看到$n\leq100$的数据，不用想，直接上dfs。由于要输出组成名单，所以用一个数组来储存最优解。题目没有说多种可能性怎么选，所以应该是默认选字典序最小，那么搜索的顺序就要讲究。再加点剪枝就可以过。
```
#include<bits/stdc++.h>
using namespace std;
int n,_max,array[105],rem[105];bool mark[105],hate[105][105];
void dfs(int now,int cnt){
if(_max<cnt){
_max=cnt;for(int i=1;i<=cnt;i++)rem[i]=array[i];
}
if(now>n||n-now+1+cnt<_max)return;
for(int i=1;i<=cnt;i++)
if(hate[array[i]][now]){dfs(now+1,cnt);return;}
array[cnt+1]=now;dfs(now+1,cnt+1);dfs(now+1,cnt);
}
int main(){
int m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;scanf("%d%d",&a,&b);hate[min(a,b)][max(a,b)]=1;
}
dfs(1,0);
printf("%d\n",_max);
for(int i=1;i<=_max;i++)mark[rem[i]]=1;
for(int i=1;i<=n;i++)printf("%d ",mark[i]);
return 0;
}
```