AT_icpc2013spring_e 最小生成树

该题目已被 CCF 征用为GESP2025年9月8级编程第二题。

洛谷 P14080 是重题。

题目

只需要考虑删除的边在不在最小生成树上

如果这条边 $(u,v)$ 不在最小生成树上，那么还是原来的答案。

如果这条边 $(u,v)$ 在最小生成树上，在最小生成树中删除这条边会把树分成两部分，那么一定需要另一条边替换。这条边一定可以把两个部分连接起来。怎么找到满足条件的边权最短的边呢？简单画图可以发现，一条边 $(u,v)$ 可以替换树上路径 $(u,v)$ 上的边。用树链剖分之类的可以维护，不过直接暴力维护也可以，CCF 没有卡掉暴力维护。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,s[N];
struct js
{
	int u,v,w,num;
}b[N];
bool cmp(js x,js y)
{
	return x.w<y.w;
}
bool cmp2(js x,js y)
{
	return x.num<y.num;
}
int f[N];
int find(int x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
vector<int> a[N];
bool bj[N];
int fa[N],dep[N];
void dfs(int x)
{
	dep[x]=dep[fa[x]]+1;
	for(int i=0;i<a[x].size();i++)
		if(a[x][i]!=fa[x])
		{
			fa[a[x][i]]=x;
			dfs(a[x][i]);
		}
}
void tiao(int x,int y,int z)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y])
		s[x]=min(s[x],z),x=fa[x];
	while(x!=y)
		s[x]=min(s[x],z),s[y]=min(s[y],z),x=fa[x],y=fa[y];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	memset(s,127,sizeof(s));
	for(int i=1;i<=m;i++)
	{
		cin>>b[i].u>>b[i].v>>b[i].w;
		b[i].num=i;
	}
	sort(b+1,b+1+m,cmp);
	for(int i=1;i<=n;i++)	
		f[i]=i;
	long long ans=0;
	
	for(int i=1;i<=m;i++)//最小生成树
	{
		if(find(b[i].u)!=find(b[i].v))
		{
			f[find(b[i].u)]=find(b[i].v);
			ans+=b[i].w;
			a[b[i].u].push_back(b[i].v);
			a[b[i].v].push_back(b[i].u);
			bj[b[i].num]=1;
		}
	}
	sort(b+1,b+1+m,cmp2);
	dfs(1);
	for(int i=1;i<=m;i++) //对树上路径u-v赋值(可以用树链剖分优化)
		if(!bj[i])
			tiao(b[i].u,b[i].v,b[i].w);
	for(int i=1;i<=m;i++)
	{
		if(!bj[i])
			cout<<ans<<"\n";
		else
		{
			int t=dep[b[i].u]>dep[b[i].v]?b[i].u:b[i].v;
			if(s[t]<=1e9)
				cout<<ans-b[i].w+s[t]<<"\n";
			else 
				cout<<-1<<"\n";
		}
	}
	return 0;
}

注：该代码可以通过洛谷，无法通过 AT，请改为树链剖分以通过。