图的m着色

题目描述:

给定无向连通图 \( 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

---

来源: 原创