TC-SRM-587-div1-900

2016.10.14 08:47 Fri | 331次阅读 | ioi2017集训队作业 | 固定链接 | 源码

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$个方程的方程组,直接高斯消元可以判断是否有解。
然而最小字典序的问题我没有想到怎么解决,并且时间复杂度也不太可行。

算法二

进一步分析,每2*2个方格的情况,可以推广到每相邻两行的情况,若一行已经确定,那另一行一定和它完全相同或完全相反,任意两行的关系也是这样。
所以,我们可以把每行看作一个点,点可以分成两类,正着填和反着填,形成一个二分图,若一列中有两行都被确定了,若都是N或都是Z,则这两行一定完全相同,这两个点连一条边权为0的边,若1N1Z,连一条边权为1的边,然后判断图是否存在奇环即可判断是否有解。
然后对于没填好的点,可以试着先填一个N,然后把该连的边连好,再判一次奇环,如果不存在,则这个点可以填N,这个点肯定是Z,再重新连一次边。

时空复杂度

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