分考场 【 DFS + 染色问题 】

试题 历届试题 分考场

资源限制

时间限制：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

样例输出

4

样例输入

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出

5

#include<iostream>
#include<bits/stdc++.h>
#include<string>
using namespace std;
int gra[200][200]; // 记录两个人之间的关系，gra[i][j] == 1 代表 i 和 j 认识
int vis[200][200]; // vis[i][j] == 1 代表第 i 间教室的第 j 人在这间教室。
int n,m;
int c[200]; // c[i] 表示第 i 个房间的人数
int ans; // 最终答案
int flag; // 在 DFS 中用于判断当前 s 是否能分配给当前教室
void dfs(int s, int tot, int num) // s 为当前的人，tot 为当前一共分配的教室，num 为当前分配到了多少人了
{
    if(tot >= ans)
    {
        return ;
    }
    if(num == n)
    {
        ans = min(ans,tot);
        return ;
    }

    for(int i = 1; i <= tot; i ++)
    {
        flag = 1; // 假设能分配
        for(int j = 1; j <= c[i]; j ++)  // c[i] 代表 i教室的总人数
        {
            if(gra[s][vis[i][j]])  // 代表 s 和 vis[i][j] 有关系，也就是第 i 间教室的第 j 同学有关系
            {
                flag = 0;
                break;
            }
        }
        if(flag)
        {
            vis[i][++c[i]] = s;
            dfs(s+1,tot,num+1);
            --c[i];
        }
    }
    vis[tot+1][++c[tot+1]] = s;
    dfs(s+1,tot+1,num+1);
    --c[tot+1];

}
int main()
{
    int u,v;
    scanf("%d\n%d", &n, &m);
    for(int i = 0; i < m; i ++)
    {
        scanf("%d %d", &u, &v);
        gra[u][v] = gra[v][u] = 1;
    }
    ans = n;
    dfs(1,0,0);
    printf("%d\n",ans);
    return 0;
}