CF1468J Road Reform 题解

题目简述

给定一个有 $n$ 个节点，$m$ 条无向带权边的图，和一个参数 $k$，第 $i$ 条边权值为 $s_i$。

现在你要保留这个图中的 $n-1$ 条边使得这个图变成一棵树，然后你可以对这棵树上的任意边进行修改，每次修改可以使这个边的权值加上一或减去一。

现在你需要使所有边权的最大值正好等于 $k$，求所有保留方案的最小操作数。

题目分析

首先，发现此题要求的是最大值等于 $k$，易想到先做出最小的情况，再调整最大值逼近 $k$，并且本题还要将一张图变成一棵树，综上所述，可以想到先求出图的最小生成树。

接下来，我们可知最小生成树的最大值，令它为 $\max$，我们可分以下三种情况尽行讨论：

• 如果 $\max\lt k$，我们可以遍历所有的边，找一条最接近 $k$ 的边，他们之间的差的绝对值便是答案。由生成树的性质可知，使这条边替换生成树的一条边后生成树仍然可以是一棵树，符合题意。
• 如果 $\max=k$，不需要调整，答案为 $0$。
• 如果 $\max\gt k$，我们应遍历所有树边，将凡是大于 $k$ 的树边都减小使它等于 $k$，并累加他们的差，这样才能符合要求。由于是最小生成树，易证此为最优解。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,t,k,fu[N],Max,a[N],b[N],cnt1;
unsigned long long ans;
struct edge
{
	int u,v,w;
	friend bool operator < (edge x,edge y)
	{
		return x.w<y.w;
	}
}e[N];
int find(int x)
{
	return fu[x]==x?x:fu[x]=find(fu[x]);
}
void solve()
{
	cin>>n>>m>>k;
	cnt1=0;
	ans=-1;
	memset(e,0,sizeof e);
	memset(fu,0,sizeof fu);
	for(int i=1;i<=n;i++)
	{
		fu[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+1+m);
	for(int i=1;i<=m;i++)
	{
		int x=e[i].u,y=e[i].v;
		if(find(x)!=find(y))
		{
			fu[find(x)]=find(y);
			Max=e[i].w;
			b[++cnt1]=e[i].w;
		}
		a[i]=e[i].w;
	}
	if(Max<k)
	{
	    for(int i=1;i<=m;i++)
	    {
	    	ans=min(ans,1ull*abs(k-a[i]));
		}
	}
	else
	{
		ans=0;
		for(int i=1;i<=cnt1;i++)
		{
			if(b[i]>=k) ans+=b[i]-k;
		}
	}
    cout<<ans<<"\n";
}
int main()
{
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}