#P18357. Edge Coloring Problem
Edge Coloring Problem
Edge Coloring Problem
输入:标准输入
输出:标准输出
题目描述
给定一张有 个顶点的简单无向图。顶点编号为 ,每个顶点的度数都恰好为 ,因此图中共有 条边。
图由 个长度为 的二进制串 表示。若 的第 个字符为 1,表示顶点 之间存在一条边;否则不存在。保证 的第 个字符为 0,并且 。
给每条边分配一个正整数作为它的颜色。如果任意两条拥有公共端点的边颜色都不同,则称为合法的边染色。
在所有合法边染色中,所使用的最大颜色编号的最小值称为图的边色数。
求这张图的边色数,并给出一种达到该边色数的合法边染色方案。
输入格式
第一行包含一个整数 。
接下来 行,第 行包含二进制串 。
输出格式
第一行输出图的边色数 。
接下来输出一个 的整数矩阵。第 行第 个整数为 :
- 如果原图存在边 ,输出分配给该边的颜色,范围为 ,且 ;
- 如果原图不存在这条边,输出 。特别地,所有 均为 。
任何达到最优颜色数的合法方案都可以接受。
数据范围
- ;
- 每个 长度均为 ,只包含 0 和 1;
- 保证输入表示一张简单无向图,且每个顶点度数均为 。
不要求原图连通。本题只有一个测试用例。
样例输入 1
6
011100
101010
110001
100011
010101
001110
样例输出 1
3
-1 2 3 1 -1 -1
2 -1 1 -1 3 -1
3 1 -1 -1 -1 2
1 -1 -1 -1 2 3
-1 3 -1 2 -1 1
-1 -1 2 3 1 -1
样例输入 2
5
01001
10100
01010
00101
10010
样例输出 2
3
-1 2 -1 -1 1
2 -1 3 -1 -1
-1 3 -1 1 -1
-1 -1 1 -1 3
1 -1 -1 3 -1
样例说明
第一组中,顶点 1 与顶点 2、3、4 相连,因此与它关联的三条边必须使用不同颜色,边色数至少为 3。样例输出给出了一种使用 3 种颜色的合法方案,所以边色数为 3。