dfs 搜索 分考场问题

蓝桥杯:分考场问题 https://www.dotcpp.com/oj/problem1874.html

题目描述

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

思路(dfs+剪枝)

这个题，一般简单的贪心法是考虑不周的，比如把和自己不认识的同学都加入一个考场，此时没有考虑其他同学之间是否相互认识。这个题可以抽象为：存在一个无向图，要求给图中的点涂色，并且有线连接的点之间不能是同一种颜色。 但是这不是四色问题，因为同学之间的关系所形成的无向图不一定是平面图，对于非平面图，所用到的颜色就可能超过四种。 所以我们每次dfs(id),判断前num个房间是不是可以放进去,不能放进去就在开辟一个房间,能放进去也不用担心是不是最优情况,我们都遍历一遍,回溯,找到最优情况

代码

#include <iostream> using namespace std; int mp[100][100];//表示关系 int room[100][100];/*一维表示第几个房间二维表示第几个人值表示放的是几号 例如 room[2][1]=5表示第二个房间第一个人是5号学生 room[2][2]=4表示第二个房间第二个放入的是4号学生*/ int cnt[100];//用来记录每个房间的人数 int n,m,ans=100;//ans最终结果不会超过100个考场 void dfs(int num,int id) { if(num>=ans) return;//num值超过ans就不用在搜了,结果肯定不是最小值 if(id==n+1) { //分完学生记录房间数 ans=min(ans,num); return ; } for(int i=1;i<=num;i++) { //每dfs下一个学生,先判断前num个房间可不可以放 int k=cnt[i];//记录第i个考试人数 int sign=1; for(int j=1;j<=k;j++) { if(mp[id][room[i][j]]) { //标记有没有相识的 sign=0; break; } } if(sign) { //没有相识的放入这个房间,这个房间人数加一 room[i][++cnt[i]]=id; dfs(num,id+1);//继续搜索 --cnt[i];//回溯,房间人数减一 } } //前num个房间都不能放,开辟新的房间,同时记录房间人数 room[num+1][++cnt[num+1]]=id; dfs(num+1,id+1); --cnt[num+1]; } int main(int argc, char const *argv[]) { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; mp[x][y]=mp[y][x]=1; } dfs(1,1); cout<<ans<<endl; return 0; }

代码解释

#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]; //是否存在关系，存在关系就是1，不存在关系就是0 int cun[maxn][maxn]; //第一维度表示的是考场，二位度里面放的是这个考场里面的学生 //cun[1][1] = 2，cun[1][2] = 0;表示考场1里面第一个存在的人是2，然后后面一位是0，也就是不存在人了，那么这时的cun[1] = 1；表示的是考场里面人的数量 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(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("%d\n",res); return 0; }