CF196E 题解

KSCD_ · 2024-09-12 17:15:16 · 题解

思路

复杂度中认为 n,m,k 同级。

发现打开第一个传送门后，打开新传送门的过程类似于 Prim 求最小生成树，也就是找到已打开点集和未打开点集之间的最短路径，然后直接传送到已打开的 S 点，再走到未打开的 T 点并打开。

显然中间走的路径是最短路，所以对 k 个点建完全图，边权为两个点在原图上的最短路径。之后在 k 个点的新图上跑最小生成树，答案即为最小生成树的权值和加上起点到传送门的最短距离。时间复杂度瓶颈在预处理两点之间最短路径，用 Dijkstra 的话大概是 O(n^2\log n)。

考虑减少新图中的边数，设 p_i 表示离 i 最近的传送门编号，dis_i 为距传送门的距离。那么对于一条权值为 w 的边 (u,v)，在新图上建边 p_u\to p_v，边权为 dis_u+dis_v+w，这样就能包含所有最终最小生成树中的边。

笔者太菜了，完全想不出这个方法，读了官方题解之后自己证明如下：

以下设 d_{i,j} 表示点 i 和点 j 之间的最短路径长度，两个集合即为上述已开启和未开启的点集。

对于最终在最小生成树中的一条边（原图中的路径） S\to T，若路径前半部分的 p_i=S，后半部分的 p_i=T，那么路径上一定存在一条边 (u,v) 满足 p_u=S 且 p_v=T。现在只需要证明路径上 p 的情况如此即可。

使用反证法，假设 S\to u 的路径上有点 x 使得 p_x\ne S，设 p_x=E，那么 x\to u 的路径上点的 p 均为 E。

若 E 与 S 属于同一集合，与 T 属于不同集合，那么由于 d_{E,u}\le d_{S,u}，可以取 E \to T 这条路径。

否则 E 与 S 属于不同集合，由于路径的包含和 p 数组的定义，有 d_{E,x}\le d_{E,u}\le d_{S,u}\le d_{u,T}\le d_{x,T}，最终得到 d_{E,x}\le d_{T,x}，可以取 S\to E 这条路径。