最小生成数

题目描述

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

输入格式

第一行包含两个整数 �,�N,M，表示该图共有 �N 个结点和 �M 条无向边。

接下来 �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复制

7

说明/提示

数据规模：

对于 20%20% 的数据，�≤5N≤5，�≤20M≤20。

对于 40%40% 的数据，�≤50N≤50，�≤2500M≤2500。

对于 70%70% 的数据，�≤500N≤500，�≤104M≤104。

对于 100%100% 的数据：1≤�≤50001≤N≤5000，1≤�≤2×1051≤M≤2×105，1≤��≤1041≤Zi​≤104。

样例解释：

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

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int p[N];
int f(int x){
    if(p[x]!=x){//判断自己是否为结点 
        p[x]=f(p[x]);//找上一级 
    }
    return p[x]; 
} 
struct node{
    int a,b,l;
}e[N];
bool cmp(node q,node w){
    return q.l<w.l;
}
int main(){
    int n,m;cin>>n>>m;
    int ans=0;//总长度
    int cnt=0;//记录边 
    for(int i=1;i<=m;i++){//输入结构体 
        cin>>e[i].a>>e[i].b>>e[i].l;
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    sort(e+1,e+m+1,cmp);//按边排序 
    for(int i=1;i<=m;i++){
        int tx=f(e[i].a);//判断结点
        int ty=f(e[i].b);//两端结点 
        if(tx!=ty){
            p[tx]=ty;
            ans+=e[i].l;
            cnt++;
        }
    }
    if(cnt==n-1){
        cout<<ans<<endl;
    }
    else
    cout<<"orz"<<endl;
    return 0;
}