分考场 【 DFS + 染色问题 】
问题 DFS 考场 染色
2023-06-13 09:15:39 时间
试题 历届试题 分考场
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
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<bits/stdc++.h>
#include<string>
using namespace std;
int gra[200][200]; // 记录两个人之间的关系，gra[i][j] == 1 代表 i 和 j 认识
int vis[200][200]; // vis[i][j] == 1 代表第 i 间教室的第 j 人在这间教室。
int n,m;
int c[200]; // c[i] 表示第 i 个房间的人数
int ans; // 最终答案
int flag; // 在 DFS 中用于判断当前 s 是否能分配给当前教室
void dfs(int s, int tot, int num) // s 为当前的人，tot 为当前一共分配的教室，num 为当前分配到了多少人了
{
if(tot >= ans)
{
return ;
}
if(num == n)
{
ans = min(ans,tot);
return ;
}
for(int i = 1; i <= tot; i ++)
{
flag = 1; // 假设能分配
for(int j = 1; j <= c[i]; j ++) // c[i] 代表 i教室的总人数
{
if(gra[s][vis[i][j]]) // 代表 s 和 vis[i][j] 有关系，也就是第 i 间教室的第 j 同学有关系
{
flag = 0;
break;
}
}
if(flag)
{
vis[i][++c[i]] = s;
dfs(s+1,tot,num+1);
--c[i];
}
}
vis[tot+1][++c[tot+1]] = s;
dfs(s+1,tot+1,num+1);
--c[tot+1];
}
int main()
{
int u,v;
scanf("%d\n%d", &n, &m);
for(int i = 0; i < m; i ++)
{
scanf("%d %d", &u, &v);
gra[u][v] = gra[v][u] = 1;
}
ans = n;
dfs(1,0,0);
printf("%d\n",ans);
return 0;
}