#P18357. Edge Coloring Problem

Edge Coloring Problem

Edge Coloring Problem

输入:标准输入
输出:标准输出

题目描述

给定一张有 NN 个顶点的简单无向图。顶点编号为 1,2,…,N1,2,\ldots,N,每个顶点的度数都恰好为 N−3N-3,因此图中共有 N(N−3)2\frac{N(N-3)}2 条边。

图由 NN 个长度为 NN 的二进制串 S1,S2,…,SNS_1,S_2,\ldots,S_N 表示。若 SiS_i 的第 jj 个字符为 1,表示顶点 i,ji,j 之间存在一条边;否则不存在。保证 SiS_i 的第 ii 个字符为 0,并且 Si,j=Sj,iS_{i,j}=S_{j,i}。

给每条边分配一个正整数作为它的颜色。如果任意两条拥有公共端点的边颜色都不同,则称为合法的边染色。

在所有合法边染色中,所使用的最大颜色编号的最小值称为图的边色数。

求这张图的边色数,并给出一种达到该边色数的合法边染色方案。

输入格式

第一行包含一个整数 NN。

接下来 NN 行,第 ii 行包含二进制串 SiS_i。

输出格式

第一行输出图的边色数 CC。

接下来输出一个 N×NN\times N 的整数矩阵。第 ii 行第 jj 个整数为 ci,jc_{i,j}:

  • 如果原图存在边 {i,j}\{i,j\},输出分配给该边的颜色,范围为 1≤ci,j≤C1\le c_{i,j}\le C,且 ci,j=cj,ic_{i,j}=c_{j,i};
  • 如果原图不存在这条边,输出 −1-1。特别地,所有 ci,ic_{i,i} 均为 −1-1。

任何达到最优颜色数的合法方案都可以接受。

数据范围

  • 4≤N≤3004\le N\le300;
  • 每个 SiS_i 长度均为 NN,只包含 0 和 1;
  • 保证输入表示一张简单无向图,且每个顶点度数均为 N−3N-3。

不要求原图连通。本题只有一个测试用例。

样例输入 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。