[HNOI模拟]通讯线路

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 linea.in 输出文件 linea.out

通讯线路(line)

题目描述:

某地区共有n座村庄,每座村庄的坐标用一对整数(x, y)表示,现在要在村庄之间建立通讯网络。通讯工具有两种,分别是需要铺设的普通线路和卫星设备。卫星设备数量有限,只能给k个村庄配备卫星设备。拥有卫星设备的村庄互相间直接通讯;铺设了线路的村庄之间也可以通讯。卫星分配是不受限制的。

问怎样合理的分配卫星和铺设线路,使得在保证每两座村庄之间都可以直接或间接地通讯的前提下,铺设线路的总长度最短。 

范围:0kn2000

输入数据:

第一行两个数,n,k

接下来n行,每行两个数描述一个村庄。

输出数据:

仅一行,代表总长度,精确到0.0001

输入样例:

20 8

137 824

761 14

68 151

194 758

149 138

314 90

809 404

964 877

471 66

177 546

73 977

397 560

928 653

199 486

736 44

985 801

621 509

444 140

88 508

556 327

输出样例:

1355.4195


中小学电脑报 NOI导刊 NOIP2012河南省实验中学培训 Day4 Exercise Problem 13