[蓝桥杯 2017 国 C] 分考场(假题:最小色数)
题目描述
n n n 个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入格式
第一行,一个整数 n ( 1 < n < 100 ) n(1<n<100) n(1<n<100),表示参加考试的人数。
第二行,一个整数 m m m,表示接下来有 m m m 行数据。
以下 m m m 行每行的格式为:两个整数 a a a, b b b,用空格分开 ( 1 ≤ a , b ≤ n ) (1 \le a,b \le n) (1≤a,b≤n) 表示第 a a a 个人与第 b b b 个人认识(编号从 1 1 1 开始)。
输出格式
一行一个整数,表示最少分几个考场。
样例 #1
样例输入 #1
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出 #1
4
样例 #2
样例输入 #2
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出 #2
5
提示
时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200;
int st[N][N];
int mp[N][N];//第i个考场的第i位同学
int n,m;
int minkey;
void dfs(int k,int res)//第k个同学,存在res个考场
{
if(res>=minkey)return;//目前的考场数大于了最优考场数,不再继续
if(k>n)//目前遍历的是n+1位同学,没有,已经遍历完了
{
minkey=min(minkey,res);//更新考场数
return ;
}
for(int i=1;i<=res;i++)//依次遍历每个考场,看有没有认识他的
{
int u=1;
while(mp[i][u]&&!st[k][mp[i][u]])//如果第i个考场的第u名同学存在且不认识,继续往后遍历
u++;
//注意这个u如果每个人都不认识的话,这个u代表的是本考场人数加一
//那么这个考场就没有第u个人,
if(!mp[i][u])//没有第u个,让第k个同学成为第u个
{
mp[i][u]=k;
dfs(k+1,res);
mp[i][u]=0;//回溯
}
}
//自己新加一个考场
mp[res+1][1]=k;
dfs(k+1,res+1);
mp[res+1][1]=0;
}
int main()
{
cin>>n>>m;
minkey=n;
while(m--)
{
int a,b;
cin>>a>>b;
st[a][b]=1;//表示ab认识
st[b][a]=1;
}
dfs(1,0);//第1个同学有0个考场
cout<<minkey;
return 0;
}