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 长边就是问题的解。

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

 

10 Trackbacks

  1. By university of kentucky hoodie pinterest.com on 十一月 18, 2018 at 12:36 上午

    university of kentucky hoodie pinterest.com

    new nike air vapormax plus 924453 100 triplehot selling nike lab air vapormax triple black 899473 003nike air max 09 jcrd pinterest.comadidas nimbus pinterest.com

  2. By nike air max boys size 4 pinterest.com on 十一月 18, 2018 at 3:08 下午

    nike air max boys size 4 pinterest.com

    Halapoulivaati Vaitai Womens Nike Philadelphia Eagles Elite Black Alternate JerseyIsaiah McKenzie of the Denver Broncos runs away from DeAndre Washington 33 Sell Nike Oakland Raiders Elite Limited Authentic NFL JerseyMens Fanatics Branded White Toronto…

  3. By unique baby toys tumblr.com on 十一月 19, 2018 at 5:28 上午

    unique baby toys tumblr.com

    kids pro line minnesota vikings custom jerseynike limited greg joseph 5 miami dolphins jerseythrowback beau brinkley 48 tennessee titans jerseymens oakland raiders giorgio tavecchio nfl pro line black player jersey

  4. By adidas samba shoes price twitter.com on 十一月 30, 2018 at 6:06 下午

    adidas samba shoes price twitter.com

    pretty satin panties twitter.combest headbands for crossfit twitter.comaqua roshe run twitter.comadrianna papell metallic lace gown twitter.com

  5. By adidas copa 2018 on 十二月 20, 2018 at 2:40 下午

    adidas copa 2018

    adidas copa mundial fgadidas copa tango 171adidas f50adidas messi 151

  6. By nike air max mens air max 2011 on 十二月 22, 2018 at 11:30 上午

    nike air max mens air max 2011

    nike zoom shoesnike zoom shoes nike zoom pegasus turboasics gelnba shoes kobe ad

  7. By nba shoes nike air foamposite on 十二月 24, 2018 at 2:34 下午

    nba shoes nike air foamposite

    nike zoom shoes nike air zoom spannba shoes nike pg 2nike air max nike air max 197nike nike free 50 2014

  8. By reebok custom shoes7 on 一月 6, 2019 at 6:41 上午

    reebok custom shoes7

    men nike tiempo mystic v ic blue 819222 443new balance women low top trainers ml574 trainers ox bloodsupra sneakers sky blue men footwearsupra shoesbig saleadidas x 16 3 turf shoes solar green core black core green

  9. delta book tickets reservations on delta flights expedia.com

    everton nike home jersey shirtorange striped palace shirt instock men s fashion clothes onfulham 18 19 home and away kitsborussia dortmund germany 2011 2012 home football shirt

  10. By sevilla fc football shirt umbro vintage child size on 一月 11, 2019 at 6:40 上午

    sevilla fc football shirt umbro vintage child size

    men s light grey alisson becker liverpool fc jersey third 13 new balance authentic short shirt soccerthe club will also be raising money for the charitywin a signed chelsea fc shirt sportslenswin a signed chelsea fc shirt sportslens

Post a Comment

You must be logged in to post a comment.