ThreeColorability

作者：邢健开 徐明宽 陈俊锟 关键词：二分图染色 贪心

题目描述

给出一个$n*m$的方格，每个方格还要连一条对角线，对角线的形状分为"N"形和"Z"形，就是主对角线和副对角线。现给你一个这样的图，有的正方形对角线连法已经确定，有的没确定，问你是否能把图补完整，使其顶点可以被3-染色。若可以，返回一组字典序最小的解(NZ形成的二维字符串)。

时间、空间限制

2s/64MB

数据范围

$1\le n,m\le 50$

分析

考虑一个2*2的方格，如果有三个点的对角线已经确定，那么第四个点的方格有唯一解。要么是4个N，要么4个Z，要么2N2Z。

算法一

把Z看作1，N看作0，可以列出$(n+1)(m+1)$个变量，$nm$个方程的方程组，直接高斯消元可以判断是否有解。

如果有解，我们需要求出其最小字典序。这需要用到在线的高斯消元：维护每一位的线性基 $B_i$，每次加入一个方程的时候，将其看作一个二进制数 $x$，从低位到高位考虑，如果当前位为 $i$，则考虑是否存在 $B_i$，如果不存在则将 $B_i$ 设为 $x$，否则将 $x$ 异或上 $B_i$，将第 $i$ 位的 1 消掉，然后进行下一步。

在字典序的考虑中，枚举这一位是 $0$ 还是 $1$，这两种操作都相当于插入一个方程并判断是否有解，这可以利用上述在线高斯消元轻松实现。这样，我们就可以按位确定，就能保证字典序最小了。

在实现中需要使用压位技巧，初步分析时间复杂度 $O({n^6\over 32})$，空间复杂度 $O({n^4\over 32})$。

如果仔细分析题目性质（见《算法三》），可以证明自由元最多只有 $O(n)$ 个，那么基也只有 $O(n)$ 个了，可以证明这个算法的时间复杂度低于 $O({n^5\over 32})$。

这种做法虽然复杂度不够优秀，但给我们提供了一个新的思路：在一般的情况下要求字典序最小的解。

算法二

进一步分析，每2*2个方格的情况，可以推广到每相邻两行的情况，若一行已经确定，那另一行一定和它完全相同或完全相反，任意两行的关系也是这样。

所以，我们可以把每行看作一个点，点可以分成两类，正着填和反着填，形成一个二分图，若一列中有两行都被确定了，若都是N或都是Z，则这两行一定完全相同，这两个点连一条边权为0的边，若1N1Z，连一条边权为1的边，然后判断图是否存在奇环即可判断是否有解。

然后对于没填好的点，可以试着先填一个N，然后把该连的边连好，再判一次奇环，如果不存在，则这个点可以填N，这个点肯定是Z，再重新连一次边。

时空复杂度

时间复杂度$O(n^2m^2)$

空间复杂度$O(nm)$

算法三

进一步分析，可以发现最后肯定可以给每行每列标记上0或1，每个方格为对应的行和列的标记的异或值（Z看作1，N看作0）。（或者说，$\forall i,j,~ cells[0][0] ~ xor ~ cells[0][j] ~ xor ~ cells[i][0] ~ xor ~ cells[i][j] = 0$，把最上面的分析用表达式写下来就能得到这个结论）

所以可以把每行每列均看作点，对于每个已经填好的格子将对应的行和列连一条边权为这个格子内容（Z看作1，N看作0）的边，然后跑二分图染色即可。

这样很容易找出字典序最小的解：可以在跑二分图染色的过程中直接贪心，首先不妨给第一行标记上0（这和标记上1是等价的），然后从左至右每一列的标记都要尽量与第一行的标记相同（以使第一行对应的格子为N），然后从上至下每一行的标记都要尽量与第一列的标记相同（以使第一列对应的格子为N）。

时空复杂度

时间复杂度$O(nm)$

空间复杂度$O(nm)$