CF662B图着色题解——zhengjun如何高效求解？

本文共计1594个文字，预计阅读时间需要7分钟。

题目：传送门游戏+游戏大意+给你一张无向图，图中每条边是蓝色或红色的，让你每次选一个点，就会把与这个点相连的边的颜色反转（红变蓝，蓝变红），求最少步数使所有边颜色一致。

题目传送门

题目大意

给你一张无向图，图中每条边是蓝色或者红色的，让你每次选一个点，就会把与这个点相连的边的颜色反转（红变蓝，蓝变红），求最少步数的方案使得最后所有边的颜色都一样。

思路

好像没有 \(2-sat\) 的题解，那我就来一发。

首先分类讨论：要么都变成红色，要么都变成蓝色。

如果一条边的颜色与当前我们期望的颜色相同，那么要么两个点都选，要么都不选，所以如果一个点不选，那么另一个点也不选，一个点选了，另一个点也要选，建图就行了，如下图。

那么同理，如果一条边的颜色与期望的颜色不同，所以，如果一个点选，另一个点就不能选，如果一个点不选，那么另一个点就必须能选，图的话，略吧。

这样我们就理出来一个 \(2-sat\) 的模型。

判断无解的情况，这就是 \(2-sat\) 的经典操作，判断 \(u,u'\) 是否处于一个强联通分量即可。

对于有解的情况，还要输出解，那么由于这个图是上下对称的，所以也就是说，如果你选了 \(i_1,i_2\dots,i_m,j_1',j_2'\dots,j_{m'}'\) 这个强联通分量，那么你也一定可以不选它，选 \(i_1',i_2'\dots,i_m',j_1,j_2\dots,j_{m'}\) 这个强联通分量，那么为了让选的个数尽可能的少，所以看看这两个东西中 \(u'\) 个数谁多谁少，加到答案里面，然后再把选的这些点放到最后的方案里面就行了。

详见代码。