题解：P8653 [蓝桥杯 2017 国 C] 分考场(假题：最小色数)

Heart_of_Iron · 2024-12-06 20:18:09 · 题解

回溯法深度搜索解空间（dfs）M 是存放关系的矩阵；room 是考场的关系矩阵。

对于当前问题 dfs(x,kc)；即是第 x 个考生，kc 个考场；从第一个考场开始找，该考场没人，直接入考场；该考场有人，遍历这些人，如果没有认识的入考场；如果有认识的就找下一个考场。

一但入了考场，就递归 dfs 找下一规模问题，知道找到一个解，和当前值比较，如果更优就更新。

代码：

#include<bits/stdc++.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;
}