自动搬运

查看原文

来自洛谷，原作者为

	JoshAlMan i人

搬运于2025-08-24 22:25:02，当前版本为作者最后更新于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)$ 可以通过。