web analytics

poj 2349 最小权值生成树

Arctic Network
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 19661 Accepted: 6141
Description

The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.

Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.
Input

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).
Output

For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.
Sample Input

1
2 4
0 100
0 300
0 600
150 750

Sample Output

212.13

分析:最小生成树。

以下大号字摘自IOI2004国家集训队论文《最小生成树算法及其应用》(吴景岳):

当正向思考受阻时, 逆向思维可能有奇效。 本题就是这样。 知道卫星设备的数量,求最小的收发距离,可能比较困难;如果知道距离求数量,就很简单了。把所有可以互相通讯的村庄连接起来, 构成一个图。 卫星设备的台数就是图的连通支的个数。

问题转化为:找到一个最小的 d,使得把所有权值大于 d 的边去掉之后,连通支的个数小于等于 k。

先看一个定理。 定理 2: 如果去掉所有权值大于 d 的边后, 最小生成树被分割成为 k 个连通支,图也被分割成为 k 个连通支。

证明:

用反证法。假设原图被分割成 k’   (k'≠k)个连通支,显然不可能 k’>k,所以k’<k。 因此在某一图的连通支中, 最小生成树被分成了至少两部分, 不妨设其为T1,T2。因为 T1 和 T2 同属于一个连通支,所以一定存在 x∈T1,y∈T2,w(x, y)≤d。又因为在整个最小生成树中,所以 x 到 y 的路径中一定存在一条权值大于d 的边(u,v) (否则 x 和 y 就不会分属于 T1 和 T2 了) , w(x, y)≤d<w(u,v), 所以把(x, y)加入,把(u,v)去掉,将得到一棵总权值比最小生成树还小的生成树。这显然是不可能的。所以,原命题成立。 (证毕)

有了这个定理, 很容易得到一个构造算法: 最小生成树的第 k 长边就是问题的解。

最小权值生成树水一水就好。

 

Post a Comment

You must be logged in to post a comment.