[JOISC2014] 水壶 题解

· · 题解

考虑一个 naive 的想法，我们把整个完全图建出来，两两建筑物之间的边权为它们的最短路径长度。然后我们希望求得一个最小的边权 x 满足只考虑 \le x 的边使得 S,T 连通。

这就是货车运输。根据 truck's trick，我们造一个最小生成树，然后考虑最小生成树上 (S,T) 路径的最大边权即可。容易用最小生成树定义证明不可能有更小的最大边权。

但是我们不可能把完全图造出来。你发现完全图上有极多废边，这种 x\to y 的边之所以废就是因为 x\to z 和 z\to y 都比它还短，那么 x\to y 就一定不会被选择到最小生成树里面。如此递归下去，我们可以把废边拆成若干条有用边。

考虑有用边满足什么性质。这里薅一张 JOI 的图：

我们对网格图进行多源 BFS 染色，这样可以求出来每个点最近的建筑物在哪里。有一个很强的性质可以证明：任何一条有用边在网格图上的路径都不会经过两种以上颜色。

Proof. 考虑 x\to z\to y，其中 x,y,z 这三者颜色互不相同，且 x,y 是建筑物。令 z' 为 z 的颜色对应的建筑物，可以证明：

所以，把废边 x\to y 拆成 x\to z' 和 z'\to y 就比原来好。一直拆下去就可以拆出有用边，而所有有用边必然满足不会经过两种以上的颜色。

考虑到任意一条边必然至少会经过两种颜色（毕竟必须要连接两个不同建筑物），所以任何一条有用边都会恰好经过两种颜色。而两种颜色必然有一个分界点。

所以做法就呼之欲出了。我们直接跑一遍多源 BFS 给网格图染色，在颜色分界点处统计加边，这样最多只会有四倍网格图大小的边，但实际上远远跑不满。弄完之后随便拉一个最小生成树算法像完全图一样做就行，稠密图推荐使用 Prim，但是 Kruskal 也过了。