CF662B Graph Coloring 题解

401rk8 · 2021-12-01 21:56:49 · 题解

已经有一篇 2-SAT 题解了，但那篇题解没有用到本题的性质，导致代码不那么简洁

分别算全变成 R 或 B 的代价取 \min，以变为 R 的单个连通块为例：

显然每个点最多翻一次。记 i 为点 i 不翻转，i+n 为点 i 翻转，连边：

然后跑 2-SAT，若 i,i+n 在同一 SCC 无解。
本题的特殊之处在于都是无向边，那么选点 i 就必须选 i 所在的连通块包含的所有点，i+1 同理，且对于 i,i+n 所在的两个连通块，\forall j\ne i 要么不在其中任意一个，要么 j,j+n 分处两个。因此对于 i,i+n 这两个 SCC，只需要贪心的选需要翻转的点数少的即可。

代码几乎都是板子，非常好写。时间复杂度 O(n)

code