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;
}

如何优化？

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