UVa 10369

Arctic Network

from Volume 7. Graph Algorithms and Implementation Techniques

Description

一个地区的几个城市要通讯。通讯的设备强度，可以决定一个城市，可以向周围距离多少的城市广播。因此，只需要几个城市连接上卫星，然后就可以向周围不停的广播。而收到广播的城市可以继续向周围的城市广播，就可以让更多的城市通讯。但是设备越牛逼，价格越高，因此只要距离刚刚好，就不需要买更牛逼的设备。输入城市的坐标和有几个卫星。输出设备应该达到的最短通讯距离。

Solution

MST，Kruskal。我们假设每个城市，都已经连上卫星。之后我们的任务，就是把这些城市连接起来，减少卫星的数量直到符合题意。我们想到Kruskal每连接一条边，就相当于把城市连接起来。因此假设有n个城市，k个卫星。我们就只需要连接n-k条边，就可以达到题目的要求。 并求由于Kruskal的边，是从小到大添加的。因此只要记录下最后一条添加的边的权值，就是最短通讯范围。