题解 CF2164E Journey

· · 题解

题解 CF2164E Journey

其他题

题意

给定 n 个点 m 条边的无向连通图，边有边权。你初始在 1 号点，每次可以选下面中的一种操作：

  1. 选择一条与当前位置相连的边，走到边的另一端并标记该边，代价为该边边权。
  2. 选择一条以当前位置为起点的路径（点和边都可以重复走），走到路径的另一端，代价为路径上编号最大的边的边权。

求标记所有边并回到 1 的最小代价。

数据范围：多测，\sum n,\sum m\le 10^6，1\le w_i\le 10^9。不保证图是简单图。

做法

官解评论区里有一个赛时自己发明出重构树的选手写的题解中算法过程比较清楚，对重构树不熟的同学可以参考。

当图有欧拉回路的时候显然可以只走一操作。

对于没有欧拉回路的情况，我们需要为度数为奇的点间进行连边使得每个点度数都变成偶数。新加入的边 (u,v) 的权值显然是通过二操作从 u 到达 v 的最小代价。

而从 u 到达 v 的代价是与路径上点的编号的瓶颈值相关的。所以对于简单路径，这其实也可以视为一种图上多次询问路径最小瓶颈的问题，使用 Kruskal 重构树（此时显然要以编号的顺序添加边）即可解决。

但二操作中允许绕路。所以除了简单路径上的必经边之外，也许可以通过绕路到一些下标更大但权值更小的边来减小代价。

这种情况下，由于每次添加的边都是下标尽量小的，所以重构树上 \text{LCA}(u,v) 到根节点路径上的各个点其实都可以是从 u 至 v 二操作的代价。所以在建出重构树之后我们可以从根节点进行一次 DFS 求出每个点到根节点路径上的最小值。

而从根往叶子走的过程中这个值显然是单调不升的，所以我们应该找尽可能深的、子树内含有两个或以上原图中奇度数点的重构树上的点并在这个时刻进行连边。

这样最终的复杂度就是 O(n\log n) 或者 O(n\alpha(n))，视并查集实现而定。