图的m着色
提交数: 341, 通过率: 62.17%, 平均分: 76.04
题目描述:
给定无向连通图 \( G \) 和 \( m \) 种不同的颜色。用这些颜色为图 \( G \) 的各顶点着色,每个顶点着一种颜色。如果有一种着色法使 \( G \) 中每条边的 \( 2 \) 个顶点着不同颜色,则称这个图是 \( m \) 可着色的。图的 \( m \) 着色问题是对于给定图 \( G \) 和 \( m \) 种颜色,找出所有不同的着色法。
对于给定的无向连通图 \( G \) 和 \( m \) 种不同的颜色,编程计算图的所有不同的着色法。
输入格式:
第 \( 1 \) 行有 \( 3 \) 个正整数 \( n \) , \( k \) 和 \( m \) ,表示给定的图 \( G \) 有 \( n \) 个顶点和 \( k \) 条边, \( m \) 种颜色。顶点编号为 \( 1, 2, \dots , n \)。接下来的\( k \) 行中,每行有 \( 2 \) 个正整数 \( u, v \) ,表示图 \( G \) 的一条边 \( (u, v ) \) 。
输出格式:
计算出的不同的着色方案数
数据范围:
\( 1 \le n \le 100, 1 \le k \le 2420, 1\le m \le 6 \)。
样例输入:
5 8 4 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5
样例输出:
48
提示:
题目中的图我们可以用一个二维数组a[i][j]存储i顶点和j顶点之间的边关系。
比如a[i][j]=1表示i和j之间有边,a[i][j]=0表示i和j之间没有边。
时间限制: 1000ms空间限制: 128MB
来源: 原创