题解：P3196 [HNOI2008] 神奇的国度

梦见云月 · 2026-10-24 09:53:25 · 题解

题目容易分析出是让你对一个弦图求最小染色，使得没有一条边两端同色。

:::info[什么是弦图]

一个环，加上若干条（不为 0）非环边。

:::

经典结论是弦图的最小染色方案是它的最大团大小。

如何证明？

考虑团上一定互不相同，所以至少是最大团的大小。

此外，弦图有一个性质，一个图是弦图，当且仅当它存在完美消除序列（PEO）。

:::info[什么是 PEO？]

把图的顶点排成一个顺序：p_1,p_2,\dots,p_n。

如果对每个 p_i，它在序列中后面的邻居两两之间都相邻，也就是这些“后邻”加上自己构成一个团，那么这个序列就是 PEO。

:::

如果我们得到了 PEO，那我们很容易得到答案。

现在问题就来到了怎么求 PEO。

依旧经典算法 MCS。

流程如下：

• 选择当前 w_x 最大的 x，把 x 后入 PEO

• 更新 x 所有没有被加入 PEO 的点，令它们 w+1。

• 重复如上操作直到构建完成。

可以用堆/桶做到 O((n+m) \log n)/O(n+m)。

考虑为啥是对的。

不会证，自己搜吧。或者背下来也行。

感性证明就是贪心。