当前位置：首页 > article >正文

[蓝桥杯]分考场

article 2025/8/19 5:49:51

题目描述

nn 个人参加某项特殊考试。

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

求是少需要分几个考场才能满足条件。

输入描述

输入格式：

第一行，一个整数 nn (1≤n≤1001≤n≤100)，表示参加考试的人数。

第二行，一个整数 mm，表示接下来有 mm 行数据。

以下 mm 行每行的格式为：两个整数 a,ba,b，用空格分开 ( 1≤a,b≤n1≤a,b≤n )表示第 aa 个人与第 bb 个人认识。

输出描述

输出一行一个整数，表示最少分几个考场。

输入输出样例

示例

输入

输出

运行限制

最大运行时间：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