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

输入格式
第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 X_i,Y_i,Z_iXi​,Yi​,Zi​，表示有一条长度为 Z_iZi​ 的无向边连接结点 X_i,Y_iXi​,Yi​。

输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例
输入 #1复制

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出 #1复制

7
说明/提示
数据规模：

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

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

对于 70\%70% 的数据，N\le 500N≤500，M\le 10^4M≤104。

对于 100\%100% 的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi​≤104。

样例解释：

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

 具体做法：（如有问题可以私信，还请各位多多包含）

include

include

include

include

include

using namespace std;
struct node{

int u,v,w,next;

bool operator < (const node &a)const{
    return w<a.w;
}//为了排序结构体，以结构体中w的值作为比较对象

//结构体储存u(起点）,v(终点),w(当前路径的权值),next(当前路径的上一条边)
}e[1010101];
int m,n;
int f[1010101];
//定义数组，为了“找爹”（往下看）；
int getf(int x){

return f[x]==x?x:f[x]=getf(f[x]);

//递归函数，找到两个点共同的"爹"(假设点a连接点b，点a也连接点c，那么点c和点b虽然不直接连接，但是两个点的“爹”也就是a是同一个爹，所以两个点依旧相连)
}
inline int kruskal(){

int val=0,cnt=0;//vla记录最小路径，cnt记录当前边数
sort(e+1,e+1+m);//排序
for(int i=1;i<=m;i++){//定义了ecnt,建议使用ecnt(不理解的见下文)
    int u=e[i].u,v=e[i].v;//找“爹”
    int xx=getf(u);
    int yy=getf(v);
    if(xx!=yy){//如果两人爹不同，那么就加边，同时记录路径的值；
        cnt++,val+=e[i].w,f[xx]=yy;//因为已经将两个点相连，所以同步两个点的“爹”（注：f[yy]=xx意思相同）
    }
    if(cnt==n-1) return val;//因为n个点，所以有n-1条边，当cnt等于n-1时，就可以跳出
}
return -1;

}
int main(){

cin>>n>>m;
for(int i=1;i<=n;i++)
    f[i]=i;
for(int i=1;i<=m;i++){
    cin>>e[i].u>>e[i].v>>e[i].w;

/*
这里建议单独开一个函数；
将输入改成int a,b,c;
cin>>a>>b>>c;
addedge(a,b,c);
在上方写一个函数(此题暂时不需要e[].next)
开始加边；
int ecnt=0;记录边数
void addedge(int u,int v,int w){

   e[++ecnt].u=u;
    e[ecnt].v=v;
    e[ecnt].w=w;

}
*/

}
int x=kruskal();
if(x==-1) 
    cout<<"orz";
else 
    cout<<x;
return 0;

}

 考虑到这是一道模板题，所以梳理思路很重要

​