思路

与<15108道路建设>同解，Kruskal硬过就行了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxm=1000005;

struct E{
    int from,next,to,dis;
}edge[maxm*2];

int n,m,u,v,w;
int head[maxn],cnt=0,fa[maxn];

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

void unite(int x,int y){
        fa[find(x)]=find(y);
}

void addedge(int from,int to,int dis){
    edge[++cnt].next=head[from];
    edge[cnt].from=from;
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

bool cmp(E a,E b){
    return a.dis<b.dis;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    int tot=0,sm=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(edge+1,edge+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        if(find(edge[i].to)!=find(edge[i].from)){
            sm+=edge[i].dis;
            unite(edge[i].to,edge[i].from);
            tot++;
        }
        if(tot==n-1) break;
    }
    cout<<sm<<endl;
    return 0;
}