[kuangbin带你飞]专题六最小生成树 G - Arctic Network

深藏阁楼爱情的钟 2023-08-17 15:41 107阅读 0赞

# G - Arctic Network #

题目链接：[https://vjudge.net/contest/66965\#problem/G][https_vjudge.net_contest_66965_problem_G]

**题目：**

**国防部（DND）希望通过无线网络连接几个北部前哨站。在建立网络时将使用两种不同的通信技术：每个前哨站都有一个无线电收发器，一些前哨站还有一个卫星信道。  
    任何带卫星频道的两个前哨站都可以通过卫星进行通信，无论其位置如何。否则，两个前哨只有当它们之间的距离不超过D时才可以通过无线电进行通信，这取决于收发器的功率。更高的功率产生更高的D但成本更高。由于采购和维护考虑，前哨的收发器必须相同;也就是说，每对前哨的D值都是相同的。  
  
    您的工作是确定收发器所需的最小D。每对前哨之间必须至少有一条通信路径（直接或间接）。  
输入  
    第一行输入包含N，即测试用例的数量。每个测试用例的第一行包含1 <= S <= 100，卫星信道的数量，并且S <P <= 500，即前哨的数量。 P线跟随，给出每个前哨的（x，y）坐标，单位为km（坐标为0到10,000之间的整数）。  
产量  
    对于每种情况，输出应由一条线组成，给出连接网络所需的最小D.输出应指定为2个小数点。  
样本输入  
  
    1  
    2 4  
    0 100  
    0 300  
    0 600  
    150 750  
  
样本输出  
  
    212.13**

**思路：s个通信工具，p个点，先求最小生成树，然后用数组cun\[\]把最小生成树的每个边存起来，由于求最小的D，所以s个通信工具用给最长的s个边，其余的就要用到无线电收发器了，故输出cun\[p-s-1\]即可，由于下标从0开始，所以减一，还有数组不要开小了，会wa。**

//
    // Created by hanyu on 2019/7/31.
    //
    #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;
    struct Node{
        int u,v;
        double w;
        bool operator<(const Node &other)const{
            return this->w<other.w;
        }
    }node[maxn];
    int father[maxn];
    double cun[maxn];
    int find(int x)
    {
        if(x==father[x])
            return x;
        return father[x]=find(father[x]);
    }
    double len(double x1,double x2,double y1,double y2)
    {
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            double xx[maxn],yy[maxn];
            for(int i=0;i<=m;i++)
                father[i]=i;
            memset(cun,0,sizeof(cun));
            for(int i=1;i<=m;i++)
            {
                scanf("%lf%lf",&xx[i],&yy[i]);
            }
            int cnt=0;
            for(int i=1;i<m;i++)
            {
                for(int j=i+1;j<=m;j++)
                {
                    double p=len(xx[i],xx[j],yy[i],yy[j]);
                    node[cnt].u=i;
                    node[cnt].v=j;
                    node[cnt++].w=p;
                }
            }
            sort(node,node+cnt);
            int book=0;
            for(int i=0;i<cnt;i++)
            {
                int uu=find(node[i].u);
                int vv=find(node[i].v);
                if(uu==vv)
                    continue;
                else
                {
                    father[uu]=vv;
                    cun[book++]=node[i].w;
                }
            }
            printf("%.2f\n",cun[m-n-1]);
        }
        return 0;
    }

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

[https_vjudge.net_contest_66965_problem_G]: https://vjudge.net/contest/66965#problem/G