问题描述
n个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入格式
第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
一行一个整数，表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
#include <iostream> #include <string.h> using namespace std; int data[105][105], ans; //data(i, j)(题目的输入)， ans(记录答案) int classes[105][105], stu_num[105]; //classes[i][j](第i个班，第j个学生的编号)， stu_num[i](第i个班的学生数量) /* 判断编号为s_id的学生，能否进入编号为cls_id的班级 */ int can_go(int s_id, int cls_id) { for(int i = 1; i <= stu_num[cls_id]; i++) { int stu = classes[cls_id][i]; if(data[s_id][stu] == 1) return 0; } return 1; } /* 从编号为s_id的学生安排教室，直到安排到编号为total_stu的学生， 返回至少需要的教室个数，且此时已经安排了total_clasa个教室 */ int solve(int s_id, int total_class, int total_stu) { if(s_id > total_stu) return total_class; if(total_class >= ans) return ans; //这句剪掉了大量的分支，不加超时 /*首先尝试让学生进入已安排的教室，只要能进就让他进，最后看看进哪个教室分配的教室数量最少*/ for(int i = 1; i <= total_class; i++) { if(can_go(s_id, i)) { stu_num[i] += 1; classes[i][stu_num[i]] = s_id; ans = min(ans, solve(s_id + 1, total_class, total_stu)); //保存必要信息，之后递归求解 stu_num[i] -= 1; //去掉之前保存的信息，为下次递归做好准备 } } /* 然后可以为这个学生新开一个教室 */ int new_class = total_class + 1; classes[new_class][++stu_num[new_class]] = s_id; ans = min(ans, solve(s_id + 1, new_class, total_stu)); stu_num[new_class] -= 1; return ans; } int main() { int n, m; cin >> n >> m; ans = n; memset(data, 0, sizeof(data)); memset(classes, 0, sizeof(classes)); memset(stu_num, 0, sizeof(stu_num)); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; data[a][b] = data[b][a] = 1; } cout << solve(1, 0, n) << endl; return 0; } 就是暴力搜索
原文链接：https://blog.csdn.net/lkrkrl/article/details/88973760?ops_request_misc=&request_id=26e6c5c5af3b47eb8cf99e7fdd16ea02&biz_id=&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~koosearch~default-13-88973760-null-null.268%5Ev1%5Econtrol&utm_term=%E6%91%A9%E6%89%98%E8%BD%A6%E8%80%83%E5%9C%BA
