分析

考虑一个最大生成树，变化为序列之后一定有一种方案满足 。所以这道题只需要求一个最大生成树即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int N = 5e5+1000;
struct E{LL x,y,w;}e[N];
LL f[N],n,m;
LL find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
bool cmp(E a,E b){return a.w > b.w;}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) f[i] = i;
    for(int i = 1;i <= m;i++) {
        cin >> e[i].x >> e[i].y >> e[i].w;
    }
    sort(e+1,e+1+m,cmp);
    LL ans = 0;
    for(int i = 1;i <= m;i++) {
        int fx = find(e[i].x),fy = find(e[i].y);
        if(fx == fy) continue;
        ans += e[i].w;
        f[fx] = fy;
    }
    cout << ans << endl;
}