图的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

---

来源: 原创