文章目录[隐藏]
试题 历届试题 分考场
资源限制
时间限制：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 样例输出
样例输入
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 样例输出
思路：
刚开始看题理解错了，以为是并查集的题（我朋友的朋友就是我的朋友），就错了，，，
后来仔细读了读题，A认识B，B认识C，但A未必认识C，所以不能用并查集做此题！
回溯法深度搜索解空间（dfs）
M是存放关系的矩阵；
room是考场的关系矩阵；
对于当前问题dfs(x,kc);
即是第x个考生，kc个考场；
从第一个考场开始找，
该考场没人，直接入考场；
该考场有人，遍历这些人，如果没有认识的入考场；
如果有认识的就找下一个考场；
一但入了考场，就递归dfs找下一规模问题，知道找到一个解，和当前值比较，如果更优就更新；
code:
#include<iostream> #include<string.h> using namespace std; int M[101][101]; int room[101][101]; int ans=99999; int n,m; void dfs(int num,int kc) { if(kc>=ans)return ; if(num>n){ ans=kc; }else{ for(int i=1;i<=kc;i++){ int k=0; while(room[i][k]&&M[num][room[i][k]]==0){ k++; } if(room[i][k]==0){ room[i][k]=num; dfs(num+1,kc); room[i][k]=0; } } room[kc+1][0]=num; dfs(num+1,kc+1); room[kc+1][0]=0; } } int main() { memset(M,0,sizeof M); memset(room,0,sizeof room); cin>>n>>m; int a,b; for(int i=0;i<m;i++){ cin>>a>>b; M[a][b]=1; M[b][a]=1; } dfs(1,1); cout<<ans; return 0; } 原文链接：https://blog.csdn.net/timelessx_x/article/details/115468647?ops_request_misc=&request_id=a4e44fc64a9d401fbe67769e67b97f80&biz_id=&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~koosearch~default-27-115468647-null-null.268%5Ev1%5Econtrol&utm_term=%E6%91%A9%E6%89%98%E8%BD%A6%E8%80%83%E5%9C%BA
