題目描述
nn?個人參加某項特殊考試。
為了公平，要求任何兩個認識的人不能分在同一個考場。
求是少需要分幾個考場才能滿足條件。
輸入描述
輸入格式：
第一行，一個整數?nn?(1≤n≤1001≤n≤100)，表示參加考試的人數。
第二行，一個整數?mm，表示接下來有?mm?行數據。
以下?mm?行每行的格式為：兩個整數?a,ba,b，用空格分開 (?1≤a,b≤n1≤a,b≤n?)表示第?aa?個人與第?bb?個人認識。
輸出描述
輸出一行一個整數，表示最少分幾個考場。
輸入輸出樣例
示例
輸入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
輸出
4
運行限制
- 最大運行時間：1s
- 最大運行內存: 256M
總通過次數: 4611??|??總提交次數: 6677??|??通過率: 69.1%
方法思路
為了解決分考場問題（即圖的著色問題），我們需要將n個人分配到盡可能少的考場中，使得任意兩個認識的人不在同一個考場。這是一個經典的圖著色問題，我們使用回溯法（DFS）結合貪心策略和剪枝優化來解決。
解決思路
算法特點
-
問題建模：將每個人看作圖中的一個節點，認識關系看作邊，問題轉化為求圖的最小色數（即用最少的顏色給圖著色，相鄰節點顏色不同）。
-
貪心初始解：使用貪心算法（Welch-Powell算法）計算初始上界，減少回溯搜索空間。
-
回溯搜索：按度數降序處理節點，嘗試將每個節點分配到現有考場或新考場。
-
剪枝優化：當當前考場數超過已知最優解時，剪枝。
-
狀態更新：遞歸嘗試所有可能分配，找到最小考場數。
#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std;int n, m; vector<vector<int>> graph; vector<int> deg; vector<vector<int>> rooms; int min_rooms = INT_MAX;// 貪心著色算法：計算初始上界 int greedyColoring(vector<int>& order) {vector<int> color(n, -1);int max_color = 0;for (int i = 0; i < n; i++) {int u = order[i];vector<bool> available(n + 1, true);for (int v = 0; v < n; v++) {if (graph[u][v] && color[v] != -1) {available[color[v]] = false;}}int c = 1;while (c <= n && !available[c]) c++;color[u] = c;max_color = max(max_color, c);}return max_color; }// 回溯搜索最小考場數 void dfs(int idx, vector<int>& order) {if (rooms.size() >= min_rooms) return; // 剪枝if (idx == n) {min_rooms = rooms.size(); // 更新最優解return;}int person = order[idx];// 嘗試放入現有考場for (int i = 0; i < rooms.size(); i++) {bool valid = true;for (int p : rooms[i]) {if (graph[person][p]) {valid = false;break;}}if (valid) {rooms[i].push_back(person);dfs(idx + 1, order);rooms[i].pop_back();}}// 嘗試新開考場rooms.push_back({person});dfs(idx + 1, order);rooms.pop_back(); }int main() {cin >> n >> m;graph.resize(n, vector<int>(n, 0));deg.resize(n, 0);// 構建圖和度數數組for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;a--; b--; // 轉換為0-indexedgraph[a][b] = 1;graph[b][a] = 1;deg[a]++;deg[b]++;}// 創建排序索引（按度數降序）vector<int> order(n);for (int i = 0; i < n; i++) order[i] = i;sort(order.begin(), order.end(), [&](int i, int j) {return deg[i] > deg[j];});// 貪心算法獲取初始上界min_rooms = greedyColoring(order);// 回溯搜索最優解rooms.clear();dfs(0, order);cout << min_rooms << endl;return 0; }代碼解釋
-
輸入處理：
-
讀取人數
n和認識關系數m -
構建鄰接矩陣
graph存儲認識關系 -
計算每個節點的度數
deg
-
-
節點排序：
-
創建索引數組
order -
按度數降序排序，優先處理度數高的節點（減少回溯分支）
-
-
貪心+回溯：先用貪心算法獲取較優解，再用回溯搜索優化
-
剪枝優化：當當前考場數≥已知最優解時剪枝
-
節點排序：按度數降序處理節點，提高剪枝效率
-
時間復雜度：最壞情況O(n!)，但通過剪枝和貪心初始解，實際運行效率較高
-
貪心初始解：
-
greedyColoring函數實現Welch-Powell算法 -
為每個節點分配可用最小顏色
-
返回使用的顏色數作為初始上界
-
-
回溯搜索：
-
dfs函數實現回溯搜索 -
參數
idx：當前處理的節點索引（在order中） -
嘗試將當前節點分配到現有考場（檢查沖突）
-
嘗試為當前節點新開考場
-
當分配的考場數超過當前最優解時剪枝
-
-
結果輸出：
-
回溯結束后輸出最小考場數
min_rooms
-
-
)
