蓝桥杯 18.分考场

分考场

原题目链接

题目描述

有 n 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

你的任务是求出最少需要分几个考场才能满足这个条件。

输入描述

• 第一行：一个整数 n，表示参加考试的人数（1 ≤ n ≤ 100）。
• 第二行：一个整数 m，表示接下来有 m 行数据。
• 接下来 m 行：每行两个整数 a, b，表示第 a 个人与第 b 个人认识（1 ≤ a, b ≤ n）。

输出描述

输出一个整数，表示最少需要的考场数。

输入样例

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出样例

4

c++代码

#include<bits/stdc++.h>

using namespace std;

vector<unordered_set<int>> st;
vector<vector<int>> arr;

int n, m, a, b, ans = INT_MAX, myclass = 0;

void dfs(int index) {
    if (myclass >= ans) return;
    if (index == n + 1) {
        ans = min(ans, myclass);
        return;
    }
    for (int i = 1; i <= myclass; i++) {
        bool key = true;
        for (int x : arr[index]) {
            if (st[i].find(x) != st[i].end()) {
                key = false;
                break;
            }
        }
        if (key) {
            st[i].insert(index);
            dfs(index + 1);
            st[i].erase(index);
        }
    }
    myclass++;
    st[myclass].insert(index);
    dfs(index + 1);
    st[myclass].erase(index);
    myclass--;
}

int main() {
    cin >> n >> m;
    arr = vector<vector<int>>(n + 1);
    st = vector<unordered_set<int>>(101);
    while(m--) {
        cin >> a >> b;
        arr[a].push_back(b), arr[b].push_back(a);
    }
    dfs(1);
    cout << ans;
    return 0;
}//by wqs

题目解析

这个题目就是个暴力题，会用题目的认识关系剪枝就行。

对于第index个人，假设当前有myclass(初始化为0)个教室，枚举1 - myclass个教室，让index加入，取最终需要教室最小的就行，当然如果这间教室有index认识的人，就枚举下一个教室，也就是剪枝。

for (int i = 1; i <= myclass; i++) {
    bool key = true;
    for (int x : arr[index]) {
        if (st[i].find(x) != st[i].end()) {
            key = false;
            break;
        }
    }
    if (key) {
        st[i].insert(index);
        dfs(index + 1);
        st[i].erase(index);
    }
}

当然还有一种情况，对于第index个人，可以去一个全新的教室

myclass++;
st[myclass].insert(index);
dfs(index + 1);
st[myclass].erase(index);
myclass--;