分考场（np完全问题，回溯法）

问题描述

　　n个人参加某项特殊考试。
　　为了公平，要求任何两个认识的人不能分在同一个考场。
　　求是少需要分几个考场才能满足条件。

输入格式

　　第一行，一个整数n(1<n<100)，表示参加考试的人数。
　　第二行，一个整数m，表示接下来有m行数据
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

　　一行一个整数，表示最少分几个考场。

样例输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

样例输出

4

样例输入

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出

5

基本思路：

回溯啊，一开始疯了没剪枝，后来想剪枝的时候发现想不到什么剪枝策略，就很难受，然后就加了一个最显而易见的剪枝就过了

代码如下：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 110;
const int inf = 0x3f3f3f3f;
int gra[maxn][maxn];
int cun[maxn][maxn];
int cnt[maxn];
int res=inf;
int n,m;
void solve(int id,int num){
if(num>=res){
return;
}
if(id>n){
res=min(res,num);
return;
}
for(int i=1;i<=num;i++){
int sz=cnt[i];
int jishu=0;
for(int j=1;j<=sz;j++){
if(gra[id][cun[i][j]]==0){
jishu++;
}
}
if(jishu==sz){
cun[i][++cnt[i]]=id;
solve(id+1,num);
cnt[i]--;
}
}
cun[num+1][++cnt[num+1]]=id;
solve(id+1,num+1);
--cnt[num+1];
}
int main(){
scanf("%d%d",&n,&m);
memset(gra,0,sizeof(gra));
memset(cnt,0,sizeof(cnt));
while(m--){
int a,b;
scanf("%d%d",&a,&b);
gra[a][b]=gra[b][a]=1;
}
solve(1,0);
printf("%dn",res);
return 0;
}