定义
最小生成树是指给定一个带权连通图 G，如果里面有一个子图 G' 中的边权和加起来最小并且使得所有的点都能两两相通。
性质
从上述的定义可以看出，最小生成树有以下性质：
-
如果图 G 中有 n 个点的话，G'中的边数为 n-1 且 G' 中不含有环。
-
最小生成树可能是一个，也可能是多个。
还有一些复杂的性质感兴趣的可以自行百度。
kruskal 算法
前置知识：并查集。
kruskal 算法的基本思想就是贪心，该算法的流程也很简单。
首先我们需要将所有的边进行排序，然后枚举每一条边，如果当前的边链接的两个点早已经间接或直接相连，我们就直接跳过，不连这条边，如果连满了 n-1 条边就直接退出循环，然后我们所选的边就构成了一棵最小生成树。
在判断当前边的两点是否已经相连的办法可以用并查集来判断，也是比较方便的做法。
根据其定义可以想到，我们要贪心的话，就得先加入边权小的边，假设只有两个点，那他的最小生成树就是两点之间边权最小的边构成，当到了三个点之后，就是从前面已经链接的所有边中覆盖的点与第三个点相连的边中挑一条边权最小的边来连，因为如果要是想要把第三个点连进去，就必须要与之前的联通图中的任意一点连一条边，经过这样不断的扩大，最终会以最小的代价连进所有点。在算法流程中，其当前连接的边是必定有一个点是在联通图中，必有一个点未连进联通图中，而当前边又是剩下的边中边权最小的，所以一定是原图中一棵最小生成树的边。
以上不理解也没关系反正是我胡扯的背板子就好了
P3366 【模板】最小生成树
code：
#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,f[N],num,ans;
struct sb{int x,y,w;}e[N];
inline int cmp(sb a,sb b){return a.w<b.w;}
inline int fid(int x){if(x==f[x])return x;else return f[x]=fid(f[x]);}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)cin>>e[i].x>>e[i].y>>e[i].w;
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
int xx=fid(e[i].x);
int yy=fid(e[i].y);
if(xx==yy)continue;
f[xx]=yy;
ans+=e[i].w;
num++;
if(num==n-1)break;
}
if(num==n-1)cout<<ans<<endl;
else cout<<"orz"<<endl;
return 0;
}