题解 P6898 【[ICPC2014 WF]Metal Processing Plant】

JoshAlMan · 2021-01-14 17:48:35 · 题解

判定性问题比较好做，可以 O(n^2) 做 2-SAT。但这样复杂度是 O(n^6)。可以枚举一条最大边，然后二分次大边（固定了最大边以后符合条件次大边的值显然是一个后缀），这样是 O(n^4 \log n )，双指针可以把 \log 去掉（然后再乱搞一下可以卡常过此题）

然后的奇偶环优化非常的神仙，考虑从大到小枚举最大边，然后把之前所有边构成的联通块用并查集维护：

• 如果构成了奇环，考虑染色后，必要条件就是在现在的图上边没有相邻的颜色，但此时已经有奇环了，所以必然不可能存在最大边 < 当前边的情况，可以做完一次直接 \text{break}
• 如果构成了偶环，那么你考虑要用到这个作为一个集合之内最大值，用到它就说明两端要同色，但这两端又隔奇数个点，所以没法做到这点，理由类似奇环，可以 \text{continue}
• 否则二分次大边做一遍

这样只会做 n \log n 次 2-SAT（别忘最大边可以是 0），总复杂度是 O(n ^3 \log n) 可以通过。