同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1926_算法设计例题：图的m着色（回溯）

2022-5-16 18:18| 发布者: Hocassian| 查看: 72| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504154932700-Problem List-采集的数据-后羿采集器.html

Pro.ID

1926

Title

算法设计例题：图的m着色（回溯）

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1926

AC

225

Submit

621

Ratio

36.23%

时间&空间限制

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色，求有多少种方法为图可m着色。

输入

输入的第一个为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是顶点数n、边数M和可用颜色数m（ n ≤ 10，M < 100，m ≤ 7 ），接下来M行，每行两个整数u和v，表示顶点u和v之间有一条边相连。（ 1 ≤ u < v ≤ n ）。

输出

Description

Input

Output

对应每个测试样例输出两行，第一行格式为"Case #: W"，其中'#'表示第几个测试样例（从1开始计），W为可m着色方案数。

Sample Input

1
5 8 5
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

Sample Output

Case 1: 360

Author

Eapink

样例输入