Top

图染色


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=110;
const int inf=0x3f3f3f3f;
int mp[maxn][maxn]; //关系
int cun[maxn][maxn]; // 第一维度表考场第二维度考场放的学生
int cnt[maxn]; //是cun数组存的学生数量
int res=inf;
int n,m;
void solve(int id,int num){ //id表示学生,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(mp[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(mp,0,sizeof(mp));
memset(cnt,0,sizeof(cnt));
while(m--){
int a,b;
scanf("%d%d",&a,&b);
mp[a][b]=mp[b][a]=1;
}
solve(1,0);
printf("%d\n",res);
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址