分考場
原題目鏈接
題目描述
有 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--;
