最小生成树（kruskal算法模版）

//kruskal算法，用优先队列解法，尽量用第一个模版
例题：挖沟：https://ac.nowcoder.com/acm/problem/17509
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;

using namespace std;

const int N = 500010;
struct node
{
    int u,v,w;
    friend bool operator < (const node &x,const node &y)
    {
        return x.w > y.w;
    }
};

int n,m,fa[N],sum;
priority_queue<node> q;

int find(int n)
{
    if(fa[n] == n) return n;
    return fa[n] = find(fa[n]);
}

void un(int a,int b)
{
    fa[find(a)] = fa[find(b)];
}

void kruskal()
{
    for(int i = 1;i <= n;i++)
    {
        fa[i] = i;
    }
    while(!q.empty())
    {
        int u = q.top().u;
        int v = q.top().v;
        int w = q.top().w;
        q.pop();
        if(find(u) != find(v))
        {
            un(u,v);
            sum += w;
        }
    }
}

int main()
{
    cin >> n >> m;
    sum=0;
    for(int i = 1;i <= m;i++) //m为边数，n为点的个数
    {
        int a,b,v;
        cin >> a >> b >> v;
        q.push({a,b,v}); //q.push这里一定要加{ }，这里比较容易出错
    }
    kruskal();
    cout << sum << endl;
    return 0;
}

//第二个模版
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;

using namespace std;
struct edge
{
    ll u,v,w;
}e[200010];

bool cmp(edge &a,edge &b)
{
    return a.w<b.w;
}

ll f[200005],n,m,ans,cnt;
ll find(ll x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void kruskal()
{
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++)
    {
        ll u=e[i].u;
        ll v=e[i].v;
        ll w=e[i].w;
        ll fu=find(u), fv=find(v);
        if(fu==fv) continue; //如果两者在一个连通图里面，continue
        ans+=w;
        f[fv]=fu; cnt++;
        if(cnt==n-1) break; //最小生成树只有n-1条边
    }
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    //每个点都自成一个连通量

    for(int i=0;i<m;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w; //输入两个端点和边的权值
    }
    kruskal();
    if(cnt!=n-1)
    {
        printf("orz");
    }
    printf("%lld",ans);
    return 0;
}