题目链接：https://www.luogu.com.cn/problem/P3366

第一种做法：Prim算法

//Prim算法
#include <bits/stdc++.h>

#define ll long long

const ll N = 1e6;
ll n,m;
ll e[N],ne[N],h[N],idx,w[N];
ll dis[N];
ll vis[N];

void add(ll aa,ll bb,ll cc){
    e[idx] = bb;
    ne[idx] = h[aa];
    w[idx] = cc;
    h[aa] = idx ++;
}

void prim(){
    for(ll i = 2; i <= n; i ++) dis[i] = 1e9;
    vis[1] = 1;
    ll too = 1;
    for(ll i = h[1]; i != -1; i = ne[i]){
        ll jj = e[i];
        dis[jj] = std::min(dis[jj],w[i]);
    }
    ll res = 0;
    while(too < n){
        ll jk = -1;
        ll re = 1e8;
        for(ll i = 1; i <= n; i ++){
            if(vis[i] == 0 && re > dis[i]){
                jk = i;
                re = dis[i];
            }
        }
        if(jk == -1){
            break;
        }
        too ++;
        res += re;
        vis[jk] = 1;
        for(ll i = h[jk]; i != -1; i = ne[i]){
            ll jj = e[i];
            if(vis[jj] == 0 && dis[jj] > w[i]){
                dis[jj] = w[i];
            }
        }
    }
    if(too < n) std::cout << "orz\n";
    else std::cout << res << "\n";
    return ;
}

int main(){
    std::cin >> n >> m;
    std::memset(h,-1,sizeof h);
    for(ll i = 1; i <= m; i ++){
        ll a,b,c;
        std::cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    prim();
    return 0;
}

第二种做法：Kruskal算法

//Kruskal算法
#include <bits/stdc++.h>

#define ll long long

const ll N = 1e6;
ll f[N];
ll n,m,k;

struct ii{
    ll a;
    ll b;
    ll c;
    friend bool operator<(ii &w1,ii &w2){
        return w1.c < w2.c;
    }
}pp[N];

ll fin(ll aa){
    if(f[aa] != aa) return f[aa] = fin(f[aa]);
    else return f[aa];
}

void unio(ll aa,ll bb){
    f[fin(aa)] = fin(bb);
}

void kl(){
    ll res = 0;
    ll num = 1;
    std::sort(pp + 1,pp + 1 + m);
    for(ll i = 1; i <= n; i ++){//初始状态下每个点的父节点都是自己本身
        f[i] = i;
    }
    for(ll i = 1; i <= m; i ++){
        ll aa = pp[i].a,bb = pp[i].b;
        if(fin(aa) != fin(bb)){
            unio(aa,bb);
            res += pp[i].c;
            num ++;
        }
    }
    if(num == n){
        std::cout << res << "\n";
    }
    else{
        std::cout << "orz\n";
    }
}

int main(){
    std::cin >> n >> m;
    for(ll i = 1; i <= m; i ++){
        ll a,b,c;
        std::cin >> a >> b >> c;
        pp[i] = {a,b,c};
    }
    kl();
}