[kuangbin带你飞]专题六最小生成树C - Building a Space Station

C - Building a Space Station

题目链接：https://vjudge.net/contest/66965#problem/C

题目：

您是空间站工程团队的成员，并在该站的施工过程中分配了一项任务。您需要编写一个计算机程序来完成任务。
空间站由许多单元组成，称为单元。所有细胞都是球形的，但它们的大小不一定是均匀的。在该站成功进入其轨道后不久，每个小区固定在其预定位置。很奇怪，两个细胞可能彼此接触，甚至可能重叠。在极端情况下，细胞可能完全包围另一个细胞。我不知道这样的安排是如何可能的。

所有细胞必须连接，因为机组成员应该能够从任何细胞走到任何其他细胞。如果，（1）A和B相互接触或重叠，（2）A和B通过“走廊”连接，或者（3）有一个单元格C，它们可以从单元格A走到另一个单元格B.从A到C，从B到C都是可能的。注意，条件（3）应该被传递解释。  
您需要设计一个配置，即哪些单元格对与走廊连接。走廊配置有一些自由。例如，如果存在三个单元A，B和C，彼此不接触或不重叠，则至少三个计划是可能的，以便连接所有三个单元。第一个是建造走廊A-B和A-C，第二个是B-C和B-A，第三个是C-A和C-B。建造走廊的成本与其长度成正比。因此，您应该选择走廊总长度最短的计划。  
您可以忽略走廊的宽度。在两个单元格表面上的点之间构建一个走廊。它可以任意长，但当然选择最短的一个。即使两个走廊A-B和C-D在空间相交，也不认为它们在（例如）A和C之间形成连接路径。换句话说，您可以认为两条走廊从不相交。

输入
输入由多个数据集组成。每个数据集以下列格式给出。

ñ  
x1 y1 z1 r1  
x2 y2 z2 r2  
...  
xn yn zn rn  
数据集的第一行包含整数n，即整数。 n是正数，不超过100。  
以下n行是细胞的描述。一行中的四个值是球体的中心的x，y和z坐标，以及球体中的半径（在问题的其余部分中称为r），按此顺序。每个值由小数部分给出，小数点后3位。值由空格字符分隔。  
x，y，z和r中的每一个都是正的并且小于100.0。  
输入的结尾由包含零的线表示。

产量
对于每个数据集，应打印走廊的最短总长度，每个都在一个单独的行中。打印的值应在小数点后3位。它们可能没有大于0.001的误差。

请注意，如果不需要走廊，也就是说，如果所有单元都没有走廊连接，则走廊的最短总长度为0.000。

样本输入

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

样本输出

20.000  
0.000  
73.834

思路：

在三维空间中给你 n 个球体的坐标和半径
如果这些球体间没有相通,则需要你去建立一些通道把所有的球体连接起来。
表面相切即可认为相通。
首先在各球体间建图,然后再按照边从小到大排序
用并查集查找两点是否属于同一联通分量【即判断这条边的两个球是否相通】
如果不属于同一联通分量，则连接即可

由于每次都是找的最短的边,所以最终所求一定是最短距离了

//
// Created by hy on 2019/7/30.
//

include

using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,m;
struct Node{
double x,y,z,r;
}node[maxn];
struct Edge{
int u,v;
double w;
bool operator<(const Edge &other)const{

   return this->w<other.w;

}
}edge[maxn];
int father[maxn];
int find(int x)
{
if(x==father[x])

   return x;

return father[x]=find(father[x]);
}
double len(Node L,Node R)
{
return sqrt((L.x-R.x)(L.x-R.x)+(L.y-R.y)(L.y-R.y)+(L.z-R.z)*(L.z-R.z));
}
double kru()
{
double ans=0;
for(int i=0;i<m;i++)
{

   int uu=find(edge[i].u);
   int vv=find(edge[i].v);
   if(uu==vv)
       continue;
   else
   {
       ans+=edge[i].w;
       father[uu]=vv;
   }

}
return ans;
}
int main()
{
while(~scanf(“%d”,&n))
{

   if(n==0)
       break;
   for(int i=0;i<=n;i++)
       father[i]=i;
   for(int i=0;i<n;i++)
       scanf("%lf%lf%lf%lf",&node[i].x,&node[i].y,&node[i].z,&node[i].r);
   m=0;
   for(int i=0;i<n;i++)
       for(int j=i+1;j<n;j++)
       {
           edge[m].u=i;
           edge[m].v=j;
           edge[m].w=max(0.0,len(node[i],node[j])-node[i].r-node[j].r);
           m++;
       }
       sort(edge,edge+m);
       printf("%.3f\n",kru());