题解 | #Forsaken喜欢独一无二的树#

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct edge{
    int a,b,w;
    bool operator < (const edge &b) const{
        return w<b.w;
    }
}edges[N];
int n,m;
int p[N];
int ffind (int x){
    if(p[x]!=x) p[x]=ffind(p[x]);
    return p[x];
}
void kruskal(){
    int ans=0;
    for(int i=0;i<m;){
        //从i开始 找到所有与i的权值相等的边 最后一个是j-1
        int j=i;
        for(;j<m;j++){
            auto [a,b,w]=edges[j];
            if(edges[i].w==w) {
                if(ffind(a)!=ffind(b)){
                    ans+=w;
                }
            }else break;
        }
        //已经找到权值相等的边 从中挑出必须保留的边 从ans中删去
        //因为ans存的是需要删除的边 所以需要保留的边要从中删去
        for(;i<j;i++){
            auto [a,b,w]=edges[i];
            a=ffind(a),b=ffind(b);//注意要把值赋给a,b 否则下面p[a]=b就错了
            if(a!=b){
                p[a]=b;
                ans-=w;
            }
        }
    }
    cout<<ans<<endl;
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edges[i]={a,b,c};
    }
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;
    kruskal();
}