CF1468J Road Reform 题解

题意：

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

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

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

\(T\) 组询问。

保证初始时给定的图满足任意两个点互相可达，没有重边或自环。

\(1\leq T\leq 10^3\)

\(1\leq n\leq2\times10^5,n-1\leq m\leq \min(\frac{n(n+1)}{2},2\times10^5)\)

\(\sum n,\sum m\leq2\times10^5,~1\leq k,s_i\leq 10^9\)

~~模拟赛A题爆零，于是有了这篇题解~~

感谢 @Roundgod老师的耐心解释 Orz

本题要根据最小生成树的情况分类讨论

如果最小生成树的最大边超过 \(k\)

则此时的最优方案即，将最小生成树上所有大于 \(k\) 的边都减成 \(k\)
如果最小生成树的最大边不超过 \(k\)

此时有两种选择
- 第一种，把最小生成树中的最大边抬到 \(k\)
- 第二种，把不在最小生成树中的一条比 \(k\) 大的边（显然要尽可能小些）加入最小生成树，然后去掉任意一条环上的边
实现的时候，用mni和mxi记录这两个值，最后去个 \(\min\) 就好了

注意，这是在最小生成树的最大边不超过 \(k\) 的前提下！

时间复杂度 \(O(m \log m)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(2e5+15)

int n,m,k,mxi,mni,res,ans,f[N],r[N];
struct Edge{int u,v,w;} e[N];
bool operator<(Edge a,Edge b){return a.w<b.w;}
void init(int n){for(int i=1; i<=n; i++) f[i]=i,r[i]=0;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v)
{
    u=find(u); v=find(v);
    if(u==v)return;
    if(r[u]<r[v]) f[u]=v;
    else
    {
        f[v]=u;
        if(r[u]==r[v]) ++r[u];
    }
}
void kruskal()
{
    sort(e+1,e+1+m);
    ans=INF; res=0; mxi=INF; mni=INF;
    for(int i=1; i<=m; i++)
    {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(w>=k)mxi=min(mxi,w-k);
        else if(w<=k)mni=min(mni,k-w);
        if(find(u)!=find(v))
        {
            merge(u,v);
            if(w>k) res+=w-k;
        }
    }
    if(res>0) ans=res;
    else ans=min(mxi,mni);
    write(ans);pc('\n');
}
void solve()
{
    // clear();
    read(n); read(m); read(k); init(n);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u); read(v); read(w);
        e[i]={u,v,w};
    }
    kruskal();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q=1; read(Q);
    while(Q--) solve();
    return 0;
}