P14080 [GESP202509 八级] 最小生成树

马上要考8级了。
真题还没做完。。。

虽然这是一道搬的原题，但还有许多值得学习的思路 （非树边替换技巧），注重思维能力
看看题。

一开始，我只会50pts做法。暴力就行了。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+10;
struct node{int u,v,w,id;	
}a[N];
int ne[N],q[N];
int n,m,cnt,ans,fa[N];
bool cmp(node a,node b){return a.w<b.w;
}
int find(int x){if(fa[x]==x)return fa[x];return fa[x]=find(fa[x]);
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++)cin>>a[i].u>>a[i].v>>a[i].w,a[i].id=i;for(int i=1;i<=n;i++)fa[i]=i;sort(a+1,a+1+m,cmp);for(int i=1;i<=m;i++){int x=find(a[i].u),y=find(a[i].v);if(x==y)continue;cnt++,ans+=a[i].w;fa[x]=y;ne[i]=1;}for(int i=1;i<=m;i++){if(!ne[i])q[a[i].id]=ans;else{for(int i=1;i<=n;i++)fa[i]=i;int cnt=0,ans=0;for(int j=1;j<=m;j++){if(j==i)continue;int x=find(a[j].u),y=find(a[j].v);if(x==y)continue;cnt++,ans+=a[j].w;fa[x]=y;}if(cnt==n-1)q[a[i].id]=ans;else q[a[i].id]=-1;}}for(int i=1;i<=m;i++)cout<<q[i]<<endl;return 0;
}

如何优化？

核心思想：如果一条树边被删除了，那么一定有一条非树边替换了这个树边。所以我们需要找到每条非树边，可以替换哪些树边。