蓝桥杯分考场（图染色问题）

迷南。 2021-07-16 16:54 370阅读 0赞

问题描述

n个人参加某项特殊考试。  
　　为了公平，要求任何两个认识的人不能分在同一个考场。  
　　求是少需要分几个考场才能满足条件。  
输入格式

第一行，一个整数n(1<n<100)，表示参加考试的人数。  
　　第二行，一个整数m，表示接下来有m行数据  
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。  
输出格式

一行一个整数，表示最少分几个考场。

## 思路 ##

DFS暴力回溯+剪枝。

大体思路是假设当前已经有n个考场，考场中已经放入了num个人，我们对于第num+1个人枚举n中的每一个考场看有没有不和此考场冲突的，如果满足条件则尝试放入，如果对于每个考场都不满足条件则新增加一个考场将第num+1个人放入，再继续对下一个人进行上述操作直到将所有人全部放到考场。细节见代码。

## code ##

#include <iostream>
    
    using namespace std;
    
    int t[105][105],cnt[1005],se[1005][105];//t记录图 cnt记录各个考场目前放的人数 se[i][j]i考场j号人是谁
    int res=1e9+5,n,m;
    
    
    bool check(int s,int num)
    { 
        for(int i=1;i<=cnt[s];i++)
        { 
            if(t[num][se[s][i]]) return false;
        }
        return true;
    
    }
    
    void dfs(int s,int num)
    { 
        if(s>=res) return;//剪枝，对于s>res的直接剪掉
        if(num>n) { res=s;return;}//更新最小的答案
        for(int i=1;i<=s;i++)
        { 
            if(check(i,num))//检查是否冲突
            { 
                se[i][++cnt[i]]=num;
                dfs(s,num+1);
                se[i][cnt[i]--]=0;//回溯
            }
        }
        se[s+1][++cnt[s+1]]=num;//之前考场都不能放，新增一个考场
        dfs(s+1,num+1);
        se[s+1][cnt[s+1]--]=0;
    }
    
    int main()
    { 
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        { 
            int a,b;cin>>a>>b;
            t[a][b]=t[b][a]=1;
        }
        dfs(1,1);
        cout<<res;
    }