CF547D Mike and Fish

题意

给定平面上n个点,将这些点染成红or蓝色,要求每行、每列红色点与蓝色点数量的差的绝对值<=1。输出方案(保证有解)

做法

对列和行抽象成点,对点((x,y))抽象成边(x-y)
对连通块内的奇度数点两两匹配连虚边,对所以边跑欧拉回路,然后交错染色,特殊条件:

  • 从起点向虚边出发,然后随便跑:仅起点可能第一条边与最后一条边同色,但由于是虚边所以会去掉

题外话

为什么窝被套路题秒了啊。。。

原文地址:https://www.cnblogs.com/Grice/p/12610369.html