Problem D:General Search
Time Limit:5000MS Memory Limit:65536KTotal Submit:13 Accepted:1
Description
试设计一个用回溯法搜索一般解空间的函数。该函数的参数包括：生成解空间中下一扩展结点的函数、结点可行性判定函数和上界函数等必要的函数，并将此函数用于解图的m着色问题。 图的m 着色问题描述如下：给定无向连通图G 和m 种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G 中每条边的2 个顶点着不同颜色，则称这个图是m 可着色的。图的m着色问题是对于给定图G和m 种颜色，找出所有不同的着色法。 编程任务： 对于给定的无向连通图G 和m种不同的颜色，编程计算图的所有不同的着色法。
Input
输入由多组测试数据组成。 每组测试数据输入的第一行有3 个正整数n，k 和m，表示给定的图G 有n(n≤7)个顶点和k(k≤10)条边，m(m≤6)种颜色。顶点编号为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
[Submit] [Go Back] [Status] [Clarify]
#include < iostream > #define MAX 110 using namespace std; class Color{ private : int n; // 图的顶点数 int m; // 图的可用颜色数 int a[MAX][MAX]; // 邻接矩阵 int x[MAX]; // 存储当前解 int sum; // 当前已经找到的可m着色方案数 public : Color(); void Set( int nn, int kk, int mm); bool Ok( int k); // 检查颜色可用性 void Backtrack( int t); int GetSum();};Color::Color() // 进行初始化工作 { sum = 0 ; memset(a, - 1 , sizeof (a)); memset(x, 0 , sizeof (x));} void Color::Set( int nn, int kk, int mm){ int i,b,c; n = nn; m = mm; for (i = 0 ;i < kk;i ++ ) { cin >> b >> c; a[b][c] = 1 ; a[c][b] = 1 ; }} bool Color::Ok( int k){ int j; for (j = 1 ;j <= n;j ++ ) { if ((a[k][j]) == 1 && (x[j] == x[k])) return false ; } return true ;} void Color::Backtrack( int t){ int i; if (t > n) sum ++ ; else { for (i = 1 ;i <= m;i ++ ) { x[t] = i; if (Ok(t)) Backtrack(t + 1 ); x[t] = 0 ; } }} int Color::GetSum(){ return sum;} int main(){ int nn,mm,kk; while (cin >> nn >> kk >> mm) { Color C; C.Set(nn,kk,mm); C.Backtrack( 1 ); cout << C.GetSum() << endl; } return 0 ;}
转载于:https://www.cnblogs.com/forever4444/archive/2009/06/04/1496287.html
