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

解题思路：

用Kruskal的方法对边排序，遇到边权相同的一段单独处理：

①不考虑两点已经在并查集内部的（边权更小）

②将其他边拿出来，若不在相同并查集，则进行合并；如果已经在，也是相同边权的边导致的，计入答案即可

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
const int maxN = 2e5+10 ;

struct EDGE {
    int u, v, val ;
    bool operator < (const EDGE &b) const {
        return val < b.val ;
    }
}edges[maxN<<1] ;

struct DSU {
    vector<int> fa, sz ;
    DSU(int n) : fa(n+1), sz(n+1) {
        for(int i=1 ; i<=n ; i++)
            fa[i] = i , sz[i] = 1 ;
    }
    int find(int x) {
        return fa[x]==x ? x : fa[x]=find(fa[x]) ;
    }
    void merge(int x, int y) {
        x = find(x), y = find(y) ;
        if(x==y)    return ;
        //fx -> fy
        if(sz[x]>sz[y])    swap(x,y) ;
        sz[y] += sz[x], fa[x]=y ;
    }
} ;

signed main() {
    int n , m;    cin >> n >> m ; 
    for(int i=1 ; i<=m ; i++) 
        cin >> edges[i].u >> edges[i].v >> edges[i].val ;
    
    DSU dsu(n) ;
    sort(edges+1, edges+m+1) ;
    int cnt = 0 , ans=0 ;
    for(int l=1 , r=1 ; l<=m&&r<=m ; r=l=r+1) {
        while(r<=m-1 && edges[r].val==edges[r+1].val)
            r++ ;
        if(l==r) {
            if(dsu.find(edges[l].u)==dsu.find(edges[l].v))
                continue ;
            dsu.merge(edges[l].u, edges[l].v) ;
            cnt++ ;
        }else {
            vector<int> v ;
            for(int i=l ; i<=r ; i++) {
                if(dsu.find(edges[i].u)==dsu.find(edges[i].v))
                    continue ;
                v.push_back(i) ;                
            }
            for(auto &i:v) {
                if(dsu.find(edges[i].u)==dsu.find(edges[i].v)) {
                    ans += edges[i].val ;
                }else 
                    dsu.merge(edges[i].u, edges[i].v) , cnt++ ;
            }
        }
    }
    cout << ans << endl ;
    return 0 ;
}