菜王的 blog

从大往小填，思考当前未填的最大值 $x$ 应该填哪儿？考虑 $\max(p_u, p_v) = x$ 的限制的情况。

• 没有该限制，只能填在任意未填孤立点上，$ans \gets ans \times cnt, cnt \gets cnt - 1$。

• 只有一个该限制：

  • 如果该限制两个端点都连了其它点，则无解。

  • 如果该限制只有一个端点连了其它点，就直接填在另一个端点上。

  • 否则任意选一个端点填并删去该限制，另一个端点变为未填孤立点，$ans \gets 2ans, cnt \gets cnt + 1$（这里新增的孤立点是只有以后更小的数字能填的）。

• 有两个或以上的该限制：

  • 如果这些限制的导出子图构成菊花图，就填在中心上，并将所有该限制删去，更新孤立点。

    • 如果该点有连边权更小的边，则无解。

  • 如果不是，就无解。

发现每种有解的情况都能将该限制删光并直接确立该点的位置，于是做完了，时间复杂度 $O(n + m)$。代码。