问题描述
n个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入格式
第一行,一个整数n(1<n<100),表示参加考试的人数。
第二行,一个整数m,表示接下来有m行数据
以下m行每行的格式为:两个整数a,b,用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
一行一个整数,表示最少分几个考场。
思路
DFS暴力回溯+剪枝。
大体思路是假设当前已经有n个考场,考场中已经放入了num个人,我们对于第num+1个人枚举n中的每一个考场看有没有不和此考场冲突的,如果满足条件则尝试放入,如果对于每个考场都不满足条件则新增加一个考场将第num+1个人放入,再继续对下一个人进行上述操作直到将所有人全部放到考场。细节见代码。
code
#include <iostream>
using namespace std;
int t[105][105],cnt[1005],se[1005][105];//t记录图 cnt记录各个考场目前放的人数 se[i][j]i考场j号人是谁
int res=1e9+5,n,m;
bool check(int s,int num)
{
for(int i=1;i<=cnt[s];i++)
{
if(t[num][se[s][i]]) return false;
}
return true;
}
void dfs(int s,int num)
{
if(s>=res) return;//剪枝,对于s>res的直接剪掉
if(num>n) {
res=s;return;}//更新最小的答案
for(int i=1;i<=s;i++)
{
if(check(i,num))//检查是否冲突
{
se[i][++cnt[i]]=num;
dfs(s,num+1);
se[i][cnt[i]--]=0;//回溯
}
}
se[s+1][++cnt[s+1]]=num;//之前考场都不能放,新增一个考场
dfs(s+1,num+1);
se[s+1][cnt[s+1]--]=0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;cin>>a>>b;
t[a][b]=t[b][a]=1;
}
dfs(1,1);
cout<<res;
}