A40828. 分考场
填空题
困难
知识点
题目描述
分考场
题目描述
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入格式：
第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识（编号从1开始）。
输出格式：
一行一个整数，表示最少分几个考场。
例如：
输入：
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
程序应该输出：
4
再比如：
输入：
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
则程序应该输出：
5
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
参考答案
const int N = 110, inf = 0x3f3f3f3f;
int e[N][N];
int vis[N][N]; // vis[i][j] = t表示第i个考场里面第j个人是t
int cnt[N]; // 记录每个考场种的学生数量（对应的vis）
int ans = inf, n, m;
void dfs(int id, int num) {// id表示第id个学生，num表示当前考场编号
if (num >= ans)return;
if (id > n) { // 学生已经安排完了
ans = min(ans, num);// 更新当前最优解（不要用min可能超时）
return;
}
for (int i = 1; i <= num; ++i) {// 先看之前分配为的考场里面能不能进去
int rnd = 0;// 表示id学生与第i个考场里面的人不认识的数量
for (int j = 1; j <= cnt[i]; ++j) // cnt[i]表示第i个考场里面的人数
if (e[id][vis[i][j]] == 0)rnd ++;
if (rnd == cnt[i]) { // 如果都不认识
vis[i][++cnt[i]] = id;
dfs(id + 1, num);
cnt[i]--;// 回溯
}
}
// 现有考场都不行，就要增加考场
vis[num + 1][++cnt[num + 1]] = id;
dfs(id + 1, num + 1);
--cnt[num + 1]; // 回溯
}
void solve() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
e[u][v] = e[v][u] = 1;
}
dfs(1, 0);
cout << ans << "\n";
}
上一题
下一题