洛谷题 P3366 【模板】最小生成树

淩亂°似流年 2023-08-17 15:40 75阅读 0赞

# 最小生成树 #

题目链接：[https://www.luogu.org/problem/P3366][https_www.luogu.org_problem_P3366]

### 题目描述 ###

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

### 输入格式 ###

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

### 输出格式 ###

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

### 输入输出样例 ###

**输入 \#1**

4 5
    1 2 2
    1 3 2
    1 4 3
    2 3 4
    3 4 3

**输出 \#1**

### 说明/提示 ###

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

样例解释：

![2259.png][]

所以最小生成树的总边权为2+2+3=7。

**思路：最小生成树的简单模板题**

//
    // Created by hy on 2019/7/28.
    //
    #include<algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    using namespace std;
    typedef long long ll;
    const int maxn=2e5+10;
    ll father[maxn];
    ll n,ans,point,m;
    struct Node{
        int u,v,w;
        bool operator<(const Node other)const{
            return this->w<other.w;
        }
    }node[maxn];
    ll find(ll x)
    {
        if(x==father[x])
            return x;
        return father[x]=find(father[x]);
    }
    void kru()
    {
        sort(node,node+m);
        for(int i=0;i<m;i++)
        {
            int uu=find(node[i].u);
            int vv=find(node[i].v);
            if(uu==vv)
                continue;
            else
            {
                father[uu]=vv;
                ans+=node[i].w;
                point++;
                if(point==n-1)
                    break;
            }
    
        }
    }
    int main()
    {
        scanf("%lld%lld",&n,&m);
        for(int i=0;i<=n;i++)
            father[i]=i;
        for(int i=0;i<m;i++)
            scanf("%lld%lld%lld",&node[i].u,&node[i].v,&node[i].w);
        ans=0,point=0;
        kru();
        printf("%lld",ans);
        if(point!=n-1)
            printf("orz");
        return 0;
    }

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

[https_www.luogu.org_problem_P3366]: https://www.luogu.org/problem/P3366
[2259.png]: /images/20230810/1bae1a192f2e4af68d7210e60d1e8d6b.png