2633: 回溯法-图的m着色问题
金币值：3
定数：8
时间限制：1.000 s
内存限制：128 M
正确：3
提交：3
正确率：100.00% 命题人：
题目描述
已知某无向图的顶点数为n，边数见输入时提供的邻接矩阵（n行n列），1<=n<=10。如果给定m种不同的颜色，问有多少种不同的可行着色方案（可行的着色方案要求图中任何相邻的顶点不能着相同的颜色）？
测试代码 复制
#include<stdio.h>
#include<string.h>
int n; //图中节点的个数
int m; //给定的颜色种类，编号从1到m
int sum=0;//保存可以着色的方案数
int x[11];//xi记录第i个顶点着的颜色编号
int a[11][11]; //表示图的邻接矩阵
int OK(int i) { //检验第i个顶点着的颜色是否与前i-1个顶点的着色有冲突
}
void backtrack(int i) {
if(i>n) {
sum++;
} else {
}
}
int main(void) {
int i,j;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
backtrack(1);
printf("%d\n",sum);
return 0;
}输入格式
第一行输入两个整数，分别表示图中的顶点数n和给定的颜色数m
第2行到第n+1行每行输入n个0或1的整数序列（每两个整数之间用一个空格隔开），表示该图对应的邻接矩阵
第2行到第n+1行每行输入n个0或1的整数序列（每两个整数之间用一个空格隔开），表示该图对应的邻接矩阵
输出格式
第n+2行输出不同的着色方案数量
输入样例 复制
3 2
0 1 1
1 0 0
1 0 0输出样例 复制
2