题解：P11095 [ROI 2021] 旅行 (Day 2)

godmoo · 2025-08-19 15:46:59 · 题解

Link & Cnblogs.

图论好题，但我比赛时就没有往边双上想啊啊啊。。。

题意： 给定一个 n 个点 m 条边的带权无向图，可能有重边，无自环。对于每个节点 u \neq 1，求出一条迹 1 \rightsquigarrow u，最小化迹上的边权最大值与边权最小值的和。n, m \le 3 \times 10 ^ 5, w \le 10 ^ 9。

\mathbf{Subtask~3.~} 所有一端点是 \mathbf 1 的边的边权为 \mathbf{10 ^ 9}

那么所有迹上的边权最大值均为 10 ^ 9，我们仅需求出边权最小值最小的迹。迹相关问题，不妨从边连通性的角度考虑。

我们知道，1 \rightsquigarrow u 上的桥是必选的，考虑进行边双缩点，那一个边双内贡献怎么处理呢？实际上，我们有如下引理：

由 Menger 定理，我们有如下基本事实：边双中，对于任意两点 x, y，存在经过 x, y 的回路。

对于 \mathbf{Lemma~1.}：

• 令 e = (u, v)，新建虚点 w 并将 e 视作 (u, w) 和 (w, v)，则删去 (u, w) 或 (w, v) 都等价于原图删去 e，不改变边连通性。
• 由基本事实，存在经过 x, w 的回路，这条回路必然经过 u, v，于是该回路是符合条件的回路。\square.

对于 \mathbf{Lemma~2.}：

• 由 \mathbf{Lemma~1.}，存在经过 x, e 的回路 C_x，当存在 C_x 使得 y \in C_x 时满足条件

• 同理，存在经过 y, e 的回路 C_y，当存在 C_y 使得 x \in C_y 时满足条件。

• 排除上述特殊情况，C_x, C_y 有公共边 e，x, y 均不在 C_x, C_y 的公共边（集）上，那么直接从 x 通过 C_x 走到 e，再按照走过 e 的方向（顺/逆时针）通过 C_y 走到 y 即可。\square.

往 \mathbf{Subtask~3.} 去靠：将所有边按边权从小到大排序，依次加边。加到边 (u, v, w) 时，钦定边权最大值为 w，套用 \mathbf{Subtask~3.} 的做法再加上 w 更新答案。\mathcal O(n ^ 2 + nm)。

\mathbf{Subtask~8.~n \le 5000}