UPD on 8/8:添加了代码。
题目:给定一张 nnn 个点 mmm 条边的无向连通图,每条边有一个边权,定义 dis(u,v)\text{dis}(u,v)dis(u,v) 为 u,vu,vu,v 的最短路。
给出 kkk 个关键点,对 kkk 个点建一个新图,其中对于每对 u,vu,vu,v 连一条权值为 dis(u,v)\text{dis}(u,v)dis(u,v) 的边。求新图 MST。
1≤k≤n,m≤5×1051\le k\le n,m\le 5\times 10^51≤k≤n,m≤5×105。
我怎么现在才知道这个 trick。模拟赛丢大分。
显然不能直接求出 k(k−1)2\frac{k(k-1)}{2}2k(k−1) 个边,考虑优化。
将 kkk 个点一起加入,跑 Dijkstra。对于每个源点分别一种颜色,给它经过的点染色。
比如说这张图,黑点为关键点:
跑最短路后的图:
感性理解一下,这个染色相当于一个类似圆的领域。
注意到一个可能的 MST 边在原路径上不可能经过超过两个颜色。
证明:
假设存在一条边先后经过了 x,y,zx,y,zx,y,z 颜色的点,且生成树中 x,zx,zx,z 连有一条边。
显然此时 dis(x,y),dis(y,z)≤dis(x,z)\text{dis}(x,y),\text{dis}(y,z)\le \text{dis}(x,z)dis(x,y),dis(y,z)≤dis(x,z)。
我们断开 x→zx\to zx→z,然后以 yyy 为一端连向 xxx 或 zzz,显然会形成一棵新生成树,而边权和更小。
所以,我们枚举每条边,判断它两端点的颜色是否不同,如果不同,将它们俩颜色所在关键点连一条边即可。
当然,假设边的两端是 u,vu,vu,v,颜色是 x,yx,yx,y,长度是 lll,加入跑 MST 的边权就是 dis(x,u)+l+dis(y,v)\text{dis}(x,u)+l+\text{dis}(y,v)dis(x,u)+l+dis(y,v),这个在跑 Dijkstra 的时候已经算好了。
这样,我们就把边数降到了 O(m)O(m)O(m)。
跑一次 Dijkstra 是 O(mlogm)O(m\log m)O(mlogm),连边跑 Kruskal 求 MST 也是 O(mlogm)O(m\log m)O(mlogm),所以总复杂度为 O(mlogm)O(m\log m)O(mlogm)。
模拟赛出的题,正式点,代码给全了。