题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 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;
}