蓝桥杯分考场
程序员文章站
2022-06-09 17:21:09
...
历届试题 分考场
时间限制:1.0s 内存限制:256.0MB
问题描述
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
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5
import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
static List<List<Integer>>list=new LinkedList<List<Integer>>();
static int n,ans=1000;
static boolean mark[][]=new boolean[101][101];
static boolean check(int t,int w) {
for(int i=0;i<list.get(t).size();i++) {
if(mark[w][list.get(t).get(i)]) {
return false;
}
}
return true;
}
static void dfs(int x) {
if(x==n+1) {
ans=Math.min(ans, list.size());
return;
}
if(list.size()>=ans) {
return ;
}
for(int i=0;i<list.size();i++) {
if(check(i,x)) {
list.get(i).add(x);
dfs(x+1);
list.get(i).remove(list.get(i).size()-1);
}
}
List<Integer> temp=new LinkedList<Integer>();
temp.add(x);
list.add(temp);
dfs(x+1);
list.remove(list.size()-1);//将刚加入的教室删去,进行回溯
}
public static void main(String[] args) {
Scanner input=new Scanner (System.in);
n=input.nextInt();
int m=input.nextInt();
for(int i=1;i<=m;i++) {
int ip1,ip2;
ip1=input.nextInt();
ip2=input.nextInt();
mark[ip1][ip2]=mark[ip2][ip1]=true;
}
dfs(1);
System.out.println(ans);
}
}
上一篇: linux下C程序从编写到执行完整过程
下一篇: c++动态库显示加载方法