解题思路:
可以抽象为无向图染色问题。相邻顶点不能染相同颜色,问至少要用多少种颜色。
用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) { 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; }
0.0分
4 人评分
C语言训练-阶乘和数* (C++代码)(直接输出样例hhhh)浏览:1158 |
简单的a+b (C语言代码)浏览:537 |
点我有惊喜!你懂得!浏览:2213 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1514 |
矩阵乘法 (C++代码)浏览:1460 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:530 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:518 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:1419 |
兰顿蚂蚁 (C++代码)浏览:1044 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:517 |