【文件属性】:
文件名称:General Search
文件大小:2KB
文件格式:TXT
更新时间:2012-06-25 12:02:20
General Search
Description
试设计一个用回溯法搜索一般解空间的函数。该函数的参数包括:生成解空间中下一扩展结点的函数、结点可行性判定函数和上界函数等必要的函数,并将此函数用于解图的m着色问题。
图的m 着色问题描述如下:给定无向连通图G 和m 种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。如果有一种着色法使G 中每条边的2 个顶点着不同颜色,则称这个图是m 可着色的。图的m着色问题是对于给定图G和m 种颜色,找出所有不同的着色法。
编程任务:
对于给定的无向连通图G 和m种不同的颜色,编程计算图的所有不同的着色法。
Input
输入由多组测试数据组成。
每组测试数据输入的第一行有3 个正整数n,k 和m,表示给定的图G 有n个顶点和k条边,m种颜色。顶点编号为1,2,…,n。接下来的k行中,每行有2个正整数u,v,表示图G 的一条边(u,v)。
Output
对应每组输入,输出的每行是计算出的不同的着色方案数。
Sample Input
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
Sample Output
48