历届试题 分考场

@ 蓝桥杯 练习系统 历届试题 PREV-53

资源限制

时间限制：1.0s 内存限制：256.0MB

---

问题描述

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

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

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

---

输入格式

第一行，一个整数n(1<n<100)，表示参加考试的人数。 第二行，一个整数m，表示接下来有m行数据 以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

---

输出格式

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

---

测试样例₁

Input： 5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5 Output： 4

测试样例₂

Input： 5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 Output： 5

---

ACcode：

import java.io.*; public class Main { static int n, min, map[]; static boolean[][] graph; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); min = 0x33333333; n = (int)in.nval; map = new int[n + 1]; graph = new boolean[n + 1][n + 1]; in.nextToken(); int v, w; while (in.nextToken() != StreamTokenizer.TT_EOF) { v = (int)(in.nval); in.nextToken(); w = (int)(in.nval); graph[v][w] = graph[w][v] = true; } dfs(1, 0); System.out.print(min); } static void dfs(int i, int cnt) { if (cnt >= min) return; if (i > n) min = min(min, cnt); else { agent: for (int k = 1; k <= cnt; k++) { for (int g = 1; g < i; g++) if (graph[i][g] && map[g] == k) continue agent; map[i] = k; dfs(i + 1, cnt); } map[i] = cnt + 1; dfs(i + 1, map[i]); } } static int min(int a, int b) { return a < b? a: b; } }

跑半天也才 80 分，最后才发现枝剪的还留了个头头

也就是 if (cnt >= min) return 这里少了个等号

这测试用例也太针对了吧

看了部分博客的代码，不是很理解为什么要去回溯，明明是道递归轨迹很清晰的题