【c++ 图论例题学习】洛谷 P3366 最小生成树

​题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 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 51 2 21 3 21 4 32 3 43 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<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>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";elsecout<<x;return 0;}

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

​