Preparing NOJ

一般解空间搜索问题

1000ms 65536K

Description:

  试设计一个用回溯法搜索一般解空间的函数。该函数的参数包括:生成解空间中下一扩展结点的函数、结点可行性判定函数和上界函数等必要的函数,并将此函数用于解图的m着色问题。

图的m 着色问题描述如下:给定无向连通图G m 种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。如果有一种着色法使G 中每条边的2 个顶点着不同颜色,则称这个图是m 可着色的。图的m着色问题是对于给定图Gm 种颜色,找出所有不同的着色法。

对于给定的无向连通图G m种不同的颜色,编程计算图的所有不同的着色法。

Input:

  1 行有3 个正整数nk m,表示给定的图G n个顶点和k条边,m种颜色。顶点编号为12,…,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

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1310

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet