问题2095--空间站

2095: 空间站

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 5
[提交] [状态] [讨论版] [命题人:]

题目描述

空间站由许多单元组成，所有单元都是球形的。在该站成功进入其轨道后不久，每个单元都固定在其预定的位置。两个单元可能彼此接触，甚至重叠。在极端情况下，一个单元可能完全包围另一个单元。所有单元都必须连接，因为机组成员应该能够从任何单元走到任何其他单元。如果存在下面三种情况，则可以从单元A走到另一个单元B：
（1）A和B相互接触或重叠；
（2）A和B通过“走廊”连接；
（3）有一个单元C，从A到C，且从B到C是可能的（传递）。
需要设计一种配置，看看用走廊连接哪些单元可以使整个空间站连通。建造走廊的成本与其长度成正比。因此，应该选择走廊总长度最短的计划。

输入

输入由多个数据集组成。每个数据集的第1行都包含一个整数n （0<n ≤100），表示单元的数量。以下n 行是对单元的描述，其中每一行都包含4个值，表示球体的中心坐标x 、y 和z ，以及球体的半径r ，每个值都为小数（小数点后3位）。x 、y 、z 和r 均为正数且小于100.0。输入的结尾由包含0的行表示。

输出

对于每个数据集，都单行输出建造走廊的最短总长度（小数点后3位）。
注意： 如果不需要建造走廊，则走廊的最短总长度为0.000。

样例输入 Copy 

3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0

样例输出 Copy 

20.000
0.000
73.834

来源/分类

最小生成树 Prim算法 Kruskal算法 
[提交] [状态]