蓝桥杯 历届试题 分考场 (DFS)-----C语言—菜鸟级
2023-06-13 09:13:12 时间
问题 1874: [蓝桥杯][2017年第八届真题]分考场
时间限制: 1Sec 内存限制: 128MB 提交: 62 解决: 12 题目描述 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 思路:可以抽象为无向图染色问题。相邻顶点不能染相同颜色,问至少要用多少种颜色。 用DFS搜搜搜。 假设 n 个人需要 kcs 个考场 ,先在 kcs 个考场 安排n 个人 如果安排不下 再增加考场数。 通过DFS +剪枝 从所有可能情况中得到最小考场数。
#include<stdio.h>
#include<string.h>
#define N 301
#define min(a,b) a>b?b:a
int gxb[N][N];//关系表
int p[N][N];// 房间状态
int num=N,n;
void DFS(int x,int kcs){//x 代表当前安排了多少个人 kcs 代表考场数
if(kcs>=num)return;//剪子
if(x==n+1){num=min(num,kcs);return;}//如果已经安排了n个人,进行判断
int j,k;
for(j=1;j<=kcs;j++){//枚举考场
k=0;
while(p[j][k]&&!gxb[x][p[j][k]])k++;//找到一个空位 并且与该考场人无关系
if(p[j][k]==0)p[j][k]=x,DFS(x+1,kcs),p[j][k]=0;//满足条件 进行下一考生
} //回溯
p[j][0]=x;
DFS(x+1,kcs+1);// 如果所有房间都不满足条件 增加房间
p[j][0]=0;//回溯
}
int main(){
int m,i,s1,s2;
memset(gxb,0,sizeof(gxb));
memset(p,0,sizeof(p));
scanf("%d\n%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&s1,&s2);
gxb[s1][s2]=gxb[s2][s1]=1;//建关系
}
DFS(1,1);
printf("%d\n",num);
return 0;
}
有疑问留言 题目测试链接:http://www.dotcpp.com/oj/problem1874.html
相关文章
- C语言 strstr函数的用法及模拟实现strstr函数「建议收藏」
- max31865C语言程序,max31865+pt100温度传感器实验代码
- C语言之格式化输出字符
- 蓝桥杯 历届试题 带分数(全排)-------------C语言—菜鸟级
- 蓝桥杯历届试题 国王的烦恼(并查集+快排)------C语言—菜鸟级
- 【C语言应用】使用查表法计算CRC8
- 【C语言】 C 语言 关键字分析 ( 属性关键字 | 常量关键字 | 结构体关键字 | 联合体关键字 | 枚举关键字 | 命名关键字 | 杂项关键字)
- 带头双向循环链表增删查改实现(C语言)
- fgets函数及其用法,C语言fgets函数详解
- Linux下C语言编程快速入门教程(linux下c编程教程)
- 基于C语言技术的Web应用程序开发与MySQL集成(c web mysql)
- MySQL中C语言使用占位符的体会(c mysql 占位符)
- C语言和MySQL实现加密技术(c mysql 加密)
- C语言中MySQL传参转义技术探究(C mysql传参转义)
- C语言获取Oracle数据库解决方案(c 获取oracle方案)