蓝桥练习题-分考场

0分考场 - 蓝桥云课 (lanqiao.cn)

思路：暴力dfs，dfs(x,room) x为待放入教室的人，room为当前最大有几号教室，对x依次遍历教室1到教室room，若某教室当前没该同学认识的人，直接放入，接着放下一个人，若room个教室里都存在x认识的人，即x不能放入任何教室，则在开辟一块新教室放入该同学，dfs结束标志，当n个同学全部安排好后，最小教室号即为所求答案；其中，若当前教室号超过原有最小号，直接返回；

C++代码：

#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f;
typedef long long ll;
ll rel[111][111];//关系表，rel[a][b]=1表示a与b认识
ll Class[111][111];//教室里分配情况，Class[i][k]=x表示第i个教室的第k个位置被x坐了
int Mini=INF;
int n,m;

void dfs(int x,int room){
 
  if(room>=Mini)return;//若超过当前最优方案，则直接退出

  if(x>n){
    Mini=min(Mini,room);
    return;
  }

  for(int i=1;i<=room;i++){
    int k=1;
    while(Class[i][k]&&!rel[x][Class[i][k]])//找到当前坐在i教室的最后一个人
    k++;
    if(Class[i][k]==0){//若此位置没人，则x坐Class[i][k]
      Class[i][k]=x;
      dfs(x+1,room);
      Class[i][k]=0;//回溯
    }
  }

  //若当前的所有教室x均不能坐，开辟一个新教室
  Class[room+1][1]=x;
  dfs(x+1,room+1);
  Class[room+1][1]=0;//回溯
}


int main(){
  // 请在此输入您的代码
  cin>>n>>m;
  int x,y;
  for(int i=1;i<=m;i++){
    cin>>x>>y;
    rel[x][y]=1;
    rel[y][x]=1;
  }
  dfs(1,1);
  cout<<Mini;

  return 0;
}

希望对有需要的人能有所帮助，欢迎大家有什么问题到评论区里一起讨论！