题意
给定平面上n个点,将这些点染成红or蓝色,要求每行、每列红色点与蓝色点数量的差的绝对值<=1。输出方案(保证有解)
做法
对列和行抽象成点,对点((x,y))抽象成边(x-y)
对连通块内的奇度数点两两匹配连虚边,对所以边跑欧拉回路,然后交错染色,特殊条件:
- 从起点向虚边出发,然后随便跑:仅起点可能第一条边与最后一条边同色,但由于是虚边所以会去掉
题外话
为什么窝被套路题秒了啊。。。
给定平面上n个点,将这些点染成红or蓝色,要求每行、每列红色点与蓝色点数量的差的绝对值<=1。输出方案(保证有解)
对列和行抽象成点,对点((x,y))抽象成边(x-y)
对连通块内的奇度数点两两匹配连虚边,对所以边跑欧拉回路,然后交错染色,特殊条件:
为什么窝被套路题秒了啊。。。