开车旅行


<mstyle mathcolor="blue"> </mstyle> \color{blue}{最初想法}

跑一次 F l o y e d Floyed Floyed, 把加油站独自提出来建一棵树, 跑最小瓶颈路, 时间复杂度 O ( N 3 ) O(N^3) O(N3) .

实际上 上方的 F l o y e d Floyed Floyed 可以换成 N N N D i j s t r a Dijstra Dijstra 的, 时间复杂度 O ( N 2 ) O(N^2) O(N2) .


<mstyle mathcolor="red"> </mstyle> \color{red}{正解部分}

与上方差不多的思路, 只不过优化了 建树过程 .

: 先说做法 : :
D i j s t r a Dijstra Dijstra 时, 将所有加油站作为起点, 同时推入 优先队列, 跑最短路, 可以以 O ( N l o g N ) O(NlogN) O(NlogN) 的复杂度得到 普通点离得最近的加油站编号 .

然后可以遍历每条边, 若两个端点离得最近的加油站不同, 则在两个加油站之间连一条经过两个端点的路径 .

最后求出最小生成树, 其余同上 .


<mtext>   </mtext> ? 为什么这样做\ ?  ?

考虑从加油站 x x x 出发可行的路线, 肯定是走最短路径到达另一个加油站 y y y .

x x x y y y 路径上存在一条边 ( u , v , w ) (u, v, w) (u,v,w) 满足距离 u u u 最近的加油站为 x x x 且距离 v v v 最近的加油站为 y y y, 那么我们会将 ( x , y , d i s t ( x , y ) ) (x, y, dist(x, y)) (x,y,dist(x,y)) 加入生成树 .

否则可以证明 x x x y y y 的路径不可能在最小生成树中出现:

  1. 找到一条边 ( u , v , w ) (u, v, w) (u,v,w), 设距离 u u u 最近的加油站为 a a a, 距离 v v v 最近的加油站为 b b b, u u u距离 x x x 近, v v v 距离 y y y 近 .

  2. 由条件可得 d i s t ( a , u ) d i s t ( x , u ) dist(a, u) \le dist(x, u) dist(a,u)dist(x,u), d i s t ( b , v ) d i s t ( y , v ) dist(b, v) \le dist(y, v) dist(b,v)dist(y,v).

  3. 因为
    d i s t ( a , b ) = d i s t ( a , u ) + d i s t ( v , b ) + w d i s t ( x , b ) = d i s t ( x , u ) + d i s t ( v , b ) + w dist(a, b) = dist(a, u) + dist(v, b) + w \\ \le dist(x, b) =dist(x, u)+dist(v, b)+w dist(a,b)=dist(a,u)+dist(v,b)+wdist(x,b)=dist(x,u)+dist(v,b)+w
    d i s t ( a , y ) = d i s t ( a , u ) + d i s t ( v , y ) + w d i t s ( x , y ) = d i s t ( x , u ) + d i s t ( v , y ) + w dist(a, y) = dist(a, u)+dist(v, y)+w \\ \le dits(x, y) = dist(x, u)+dist(v, y)+w dist(a,y)=dist(a,u)+dist(v,y)+wdits(x,y)=dist(x,u)+dist(v,y)+w

  4. 所以从 x x x y y y 不会 比
    x x x b b b 再 从 b b b a a a 最后从 a a a y y y 更优 .

以上证明来自 wjz 的 ppt


<mstyle mathcolor="red"> </mstyle> \color{red}{实现部分}

略 .