[蓝桥杯]分考场

题目描述

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）结合贪心策略和剪枝优化来解决。

解决思路

算法特点

1. 问题建模：将每个人看作图中的一个节点，认识关系看作边，问题转化为求图的最小色数（即用最少的颜色给图着色，相邻节点颜色不同）。

2. 贪心初始解：使用贪心算法（Welch-Powell算法）计算初始上界，减少回溯搜索空间。

3. 回溯搜索：按度数降序处理节点，尝试将每个节点分配到现有考场或新考场。

4. 剪枝优化：当当前考场数超过已知最优解时，剪枝。

5. 状态更新：递归尝试所有可能分配，找到最小考场数。

   #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;
   }

   代码解释

6. 输入处理：

   • 读取人数n和认识关系数m

   • 构建邻接矩阵graph存储认识关系

   • 计算每个节点的度数deg

7. 节点排序：

   • 创建索引数组order

   • 按度数降序排序，优先处理度数高的节点（减少回溯分支）

8. 贪心+回溯：先用贪心算法获取较优解，再用回溯搜索优化

9. 剪枝优化：当当前考场数≥已知最优解时剪枝

10. 节点排序：按度数降序处理节点，提高剪枝效率

11. 时间复杂度：最坏情况O(n!)，但通过剪枝和贪心初始解，实际运行效率较高

    • 贪心初始解：

      • greedyColoring函数实现Welch-Powell算法

      • 为每个节点分配可用最小颜色

      • 返回使用的颜色数作为初始上界

    • 回溯搜索：

      • dfs函数实现回溯搜索

      • 参数idx：当前处理的节点索引（在order中）

      • 尝试将当前节点分配到现有考场（检查冲突）

      • 尝试为当前节点新开考场

      • 当分配的考场数超过当前最优解时剪枝

    • 结果输出：

      • 回溯结束后输出最小考场数min_rooms