[kuangbin带你飞]专题六最小生成树 D - Constructing Roads

傷城~ 2023-08-17 15:41 101阅读 0赞

# D - Constructing Roads #

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

**题目：**

**有N个村庄，编号从1到N，你应该建造一些道路，使每两个村庄可以相互连接。我们说两个村A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村C以便在A和C之间有一条道路，并且C和B相连。  
  
    我们知道一些村庄之间已经有一些道路，你的工作就是修建一些道路，使所有村庄都连通起来，所有道路的长度都是最小的。  
输入  
    第一行是整数N（3 <= N <= 100），这是村庄的数量。然后是N行，其中第i个包含N个整数，这些N个整数中的第j个是村庄i和村庄j之间的距离（距离应该是\[1,1000\]内的整数）。  
  
    然后是整数Q（0 <= Q <= N \*（N + 1）/ 2）。然后是Q行，每行包含两个整数a和b（1 <= a <b <= N），这意味着村庄a和村庄b之间的道路已经建成。  
产量  
    您应该输出一个包含整数的行，该整数是要构建的所有道路的长度，以便连接所有村庄，并且此值最小。  
样本输入  
  
    3  
    0 990 692  
    990 0 179  
    692 179 0  
    1  
    1 2  
  
样本输出  
  
    179**

**思路：只要求最小生成树就行，运用到并查集，详解**

//
    // 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 father[maxn];
    struct Node{
        int u,v,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 n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            father[i]=i;
        int m=0;
        int t;
        for(int i=1;i<=n;i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &t);
                node[m].u = i;
                node[m].v = j;
                node[m++].w = t;
            }
        }//加权值
        sort(node,node+m);//排序m条边
        int q;
        scanf("%d",&q);
        int x,y;
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&x,&y);
            int xx=find(x);
            int yy=find(y);
            if(xx==yy)
                continue;
            else
                father[xx]=yy;//如果输入的不连通，则合并
        }
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            int aa=find(node[i].u);
            int bb=find(node[i].v);
            if(aa!=bb)
            {
                ans+=node[i].w;
                father[aa]=bb;
            }//找每条路，如果不连通，则累加权值，并合并起来
        }
        printf("%d\n",ans);
        return 0;
    }

**见注释**

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

[https_vjudge.net_contest_66965_problem_D]: https://vjudge.net/contest/66965#problem/D