分考场

[蓝桥杯 2017 国 C] 分考场(假题：最小色数)

题目描述

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

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

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

输入格式

第一行，一个整数 $n(1<n<100)$，表示参加考试的人数。

第二行，一个整数 $m$，表示接下来有 $m$ 行数据。

以下 $m$ 行每行的格式为：两个整数 $a$，$b$，用空格分开 $(1\le a,b\le n)$ 表示第 $a$ 个人与第 $b$ 个人认识（编号从 $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;
}