[kuangbin带你飞]专题六最小生成树 H - Highways

矫情吗；* 2021-10-19 04:34 264阅读 0赞

# H - Highways #

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

题目：

Flatopia岛国完全平坦。不幸的是，Flatopia的公共高速公路系统非常糟糕。弗拉托利亚政府意识到了这个问题，并且已经建造了一些连接一些最重要城镇的高速公路。但是，仍有一些城镇无法通过高速公路抵达。有必要建造更多的高速公路，以便能够在不离开高速公路系统的情况下在任何一对城镇之间行驶。  
  
    Flatopian城镇的编号从1到N，城镇i的位置由笛卡尔坐标（xi，yi）给出。每条高速公路连接两个城镇。所有高速公路（原始高速公路和要建造的高速公路）都遵循直线，因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路都可以在两个方向使用。高速公路可以自由地相互交叉，但司机只能在位于两条高速公路尽头的小镇的高速公路之间切换。  
  
    Flatopian政府希望最大限度地降低建设新高速公路的成本。但是，他们希望保证每个城镇都可以从其他城镇到达公路。由于Flatopia是如此平坦，高速公路的成本总是与其长度成正比。因此，最便宜的高速公路系统将是最小化总公路长度的系统。  
输入  
    输入包括两部分。第一部分描述了该国的所有城镇，第二部分描述了所有已建成的高速公路。  
  
    输入文件的第一行包含一个整数N（1 <= N <= 750），表示城镇数量。接下来的N行每行包含两个整数，xi和yi由空格分隔。这些值给出了第i个城镇的坐标（对于i从1到N）。坐标的绝对值不超过10000.每个城镇都有一个独特的位置。  
  
    下一行包含单个整数M（0 <= M <= 1000），表示现有高速公路的数量。接下来的M行每行包含一对由空格分隔的整数。这两个整数给出了一对已经通过高速公路连接的城镇号码。每对城镇至少由一条高速公路连接。  
产量  
    为每条新高速公路写一条输出线，以便连接所有城镇，尽可能减少新高速公路的总长度。每条高速公路都应该通过打印这条高速公路连接的城镇号码来展示，并以空间隔开。  
  
    如果不需要建立新的高速公路（所有城镇都已连接），则应创建输出文件，但应该为空。  
样本输入  
  
    9  
    1 5  
    0 0  
    3 2  
    4 5  
    5 1  
    0 4  
    5 2  
    1 2  
    5 3  
    3  
    1 3  
    9 7  
    1 2  
  
样本输出  
  
    1 6  
    3 7  
    4 9  
    5 7  
    8 3

**思路:先求出两个点之间的距离存起来，然后给出的M个高速公路合并，然后遍历整个城镇，把祖先不同的输出即可，注意下标，城镇编号是从1开始的**

//
    // 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=2e7+7;
    int father[maxn];
    double x[maxn],y[maxn];
    struct Node{
        int u,v;
        double w;
        bool operator<(const Node &other)const{
            return this->w<other.w;
        }
    }node[maxn];
    int find(int x)
    {
        if(x==father[x])
            return x;
        return father[x]=find(father[x]);
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int i=1;i<=T;i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
        }
        for(int i=0;i<=T;i++)
            father[i]=i;
        int m=1;
        for(int i=1;i<=T-1;i++)
        {
            for(int j=i+1;j<=T;j++)
            {
                node[m].u=i;
                node[m].v=j;
                node[m++].w=sqrt(double(x[i]-x[j])*(x[i]-x[j])+double(y[i]-y[j])*(y[i]-y[j]));
            }
        }
        m--;
        sort(node+1,node+m+1);
        int n;
        scanf("%d",&n);
        int p,q;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&p,&q);
            int pp=find(p);
            int qq=find(q);
            if(pp==qq)
                continue;
            else
            {
               if(pp<qq)
                father[pp]=qq;
                else
                    father[qq]=pp;
            }
        }
        for(int i=1;i<=m;i++)
        {
            int uu=find(node[i].u);
            int vv=find(node[i].v);
            if(uu==vv)
                continue;
            else
            {
                if(uu<vv)
                   father[uu]=vv;
                else
                    father[vv]=uu;
                printf("%d %d\n",node[i].u,node[i].v);
             
            }
        }
        return 0;
    }

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

[https_vjudge.net_contest_66965_problem_H]: https://vjudge.net/contest/66965#problem/H