题目大意
将 \(n\) 个人分成 \(T\) 组，要求每组不能包含敌对的人，问有多少种分法。
思路分析
注意到 \(n,T\) 均很小，考虑爆搜。
注意到直接枚举会枚举到分组顺序的全排列，所以可以强行嵌定大小关系去重。
void dfs(int s){
if(s==n+1){
for(int i=1;i<=t;i++) if(!tt[i]) return ;
for(int i=2;i<=t;i++) if(sk[i-1][1]>sk[i][1]) return ;//去重
ans++;
return ;
}
for(int i=1;i<=t;i++){
int flag=0;
for(int j=1;j<=tt[i];j++) if(bad[sk[i][j]][s]){flag=1;break;}//判断敌对
if(flag) continue;
sk[i][++tt[i]]=s;
dfs(s+1);
tt[i]--;
}
}
正常搜索的时间复杂度为 \(O(T^n)\)，无法通过，于是加一点点剪枝：
-
如果当前人数小于当前的空组数，那么填到最后一定存在空组，直接返回。
-
每次搜索都优先判定是否合法。
然后就飞过去了。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=110;
int ans,n,t,m,in1,in2;
int bad[N][N],sk[N][N],tt[N];
void dfs(int s){
for(int i=2;i<=t;i++)
if(tt[i-1]&&tt[i]&&sk[i-1][1]>sk[i][1]) return ;
int cnt=0;
for(int i=1;i<=t;i++)
if(!tt[i]) cnt++;
if(n-s+1<cnt) return ;
if(s==n+1){
for(int i=1;i<=t;i++) if(!tt[i]) return ;
ans++;
return ;
}
for(int i=1;i<=t;i++){
int flag=0;
for(int j=1;j<=tt[i];j++) if(bad[sk[i][j]][s]){flag=1;break;}
if(flag) continue;
sk[i][++tt[i]]=s;
dfs(s+1);
tt[i]--;
}
}
int main(){
scanf("%d%d%d",&n,&t,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&in1,&in2);
bad[in1][in2]=bad[in2][in1]=1;
}
dfs(1);
cout<<ans<<'\n';
return 0;
}