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

曾经终败给现在 2023-08-17 15:41 106阅读 0赞

# C - Building a Space Station #

题目链接：[https://vjudge.net/contest/66965\#problem/C][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<algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    #include<math.h>
    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());
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11272860.html

[https_vjudge.net_contest_66965_problem_C]: https://vjudge.net/contest/66965#problem/C