蓝桥杯 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--;