最大生成树模板

最大生成树是通过先对边权进行一个排序，然后对排序后的边权进行提取，看两端的点是否联通，也就是利用并查集进行一个优化，如果两点还未在同一个集合里面，则累加边权到最后的答案，合并两个点即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
const int N=5e5+1000; 
struct node{
    ll x,y,w;
}Node[N];
ll fa[N],n,m;
bool cmp(node a,node b){
    return a.w>b.w;
}
ll find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)  fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>Node[i].x>>Node[i].y>>Node[i].w;
    }
    sort(Node+1,Node+1+m,cmp);
    ll ans=0;
    for(int i=1;i<=m;i++){
        int fx=find(Node[i].x),fy=find(Node[i].y);
        if(fx==fy) continue;
        ans+=Node[i].w;
        fa[fx]=fy;
    }
    cout<<ans<<endl;
    return 0;
}