[kuangbin带你飞]专题六最小生成树 B - Networking

﹏ヽ暗。殇╰゛Y 2023-08-17 15:40 58阅读 0赞

# B - Networking #

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

**题目**：

您被分配设计广泛区域中某些点之间的网络连接。您将获得该区域中的一组点，以及可连接成对点的电缆的一组可能路线。对于两点之间的每条可能路线，您将获得连接该路线上的点所需的电缆长度。请注意，两个给定点之间可能存在许多可能的路径。假设给定的可能路线（直接或间接）连接该区域中的每两个点。  
    您的任务是为该区域设计网络，以便在每两个点之间存在连接（直接或间接）（即，所有点都是互连的，但不一定是通过直接电缆），并且总长度为用过的电缆很小。  
输入  
    输入文件由许多数据集组成。每个数据集定义一个必需的网络。集合的第一行包含两个整数：第一行定义给定点的数量P，第二行定义点之间给定路径的数量R.以下R行定义了点之间的给定路线，每条线给出三个整数：前两个数字标识点，第三个给出路线的长度。数字用空格分隔。仅给出一个数字P = 0的数据集表示输入的结束。数据集用空行分隔。  
    最大点数为50.给定路线的最大长度为100.可能的路线数量不受限制。节点用1和P（含）之间的整数标识。两个点i和j之间的路线可以给出为i j或j i。  
产量  
    对于每个数据集，在单独的行上打印一个数字，该行显示用于整个设计网络的电缆的总长度。  
样本输入  
  
    1 0  
  
    2 3  
    1 2 37  
    2 1 17  
    1 2 68  
  
    3 7  
    1 2 19  
    2 3 11  
    3 1 7  
    1 3 5  
    2 3 89  
    3 1 91  
    1 2 32  
  
    5 7  
    1 2 5  
    2 3 7  
    2 4 8  
    4 5 11  
    3 5 10  
    1 5 6  
    4 2 12  
  
    0  
  
样本输出  
  
    0  
    17  
    16  
    26

**思路：求最小生成树**

//
    // Created by hy on 2019/7/30.
    //
    #include<algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    using namespace std;
    typedef long long ll;
    const int maxn=2e5+10;
    struct Node{
        int from,to,value;
        bool operator<(const Node &other)const{
            return this->value<other.value;
        }
    }node[maxn];
    int father[maxn];
    int find(int x)
    {
        if(x==father[x])
            return x;
        return father[x]=find(father[x]);
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            int res=0,point=0;
            if(n==0)
                break;
            for(int i=0;i<=n;i++)
                father[i]=i;
            for(int i=0;i<m;i++)
                scanf("%d%d%d",&node[i].from,&node[i].to,&node[i].value);
            sort(node,node+m);
            for(int i=0;i<m;i++)
            {
                if(find(node[i].from)==find(node[i].to))
                    continue;
                else
                {
                    res+=node[i].value;
                    father[find(node[i].from)]=find(node[i].to);
                    point++;
                    if(point==n-1)
                        break;
                }
            }
            printf("%d\n",res);
        }
        return 0;
    }

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

[https_vjudge.net_contest_66965_problem_B]: https://vjudge.net/contest/66965#problem/B