CF2275G Ranges 题解

· · 题解

我们把答案拆成好几个部分，并考虑分别求解。

  1. 拆除不影响连通性的边：因为拆除这些边只会带来收益且没有额外代价，我们尽可能拆除那些较大的边。

    • 那么我们可以最开始跑一个最小生成树，用 Kruskal，如果过程中某条边没有被加入，就将其收益加进答案。

  2. 将所有连通块串起来：如果目前有 k 个连通块，则要先连 k-1 条基础边。

    • 最开始最小生成树的时候不是维护了并查集嘛，直接根据这个并查集算出来有 k 个连通块，代价为 (1+2+\dots+k) \times x 也就是 \frac{k(k+1)}{2} \times x。

  3. 换旧买新：做完上面的操作已经完成了题目要求，但某些边可能过贵，可以选择卖掉后重新买入以赚取一定差价。

    • 因为前面已经有了 k-1 条基础边需要增加，所以后续第 i 条新边的代价为 (k+i-1)x。
    • 为了最优，我们肯定尽可能选取那些贵的边卖出再买入，因此可以把最小生成树中的边的边权从大到小排序。
    • 此时代价升序而收益降序，因此一定存在某个位置，使得前面的边是正收益，后面的边是负收益。这里的收益表示为当前边的边权减去重新买入的价格。
    • 上述位置可以通过二分找出，那么只需将前面正收益的边带来的收益全部加上即可。

然后就做完了。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
struct node{LL x,y,w;}ln[N];
int T,n,m,Q,fa[N];
bool vis[N];
LL tot,d[N],P,sum[N],Bas;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int FF(int x){return (fa[x]==x?x:fa[x]=FF(fa[x]));}
void init(){
    for(int i=1;i<=n;i++)fa[i]=i;
    return;
}
bool cmp(node d1,node d2){return d1.w<d2.w;}
bool cmp2(LL x,LL y){return x>y;}
LL Find(LL val){
    LL l=1,r=tot,res=0;
    while(l<=r){
        LL mid=(l+r)>>1;
        if(d[mid]>=(mid+Bas)*val)res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}
int main(){
    T=read();
    while(T--){
        n=read(),m=read(),Q=read();
        for(int i=1;i<=m;i++)
            ln[i].x=read(),ln[i].y=read(),ln[i].w=read();
        sort(ln+1,ln+m+1,cmp);
        init();tot=0,P=0;
        for(int i=1;i<=m;i++){
            int x=ln[i].x,y=ln[i].y;
            int fx=FF(x),fy=FF(y);
            if(fx!=fy)fa[fx]=fy,d[++tot]=ln[i].w;
            else P+=ln[i].w;
        }
        sort(d+1,d+tot+1,cmp2);
        sum[0]=0;
        for(int i=1;i<=tot;i++)sum[i]=sum[i-1]+d[i];
        Bas=-1;
        for(int i=1;i<=n;i++)vis[i]=0;
        for(int i=1;i<=n;i++){
            int fx=FF(i);
            if(!vis[fx])vis[fx]=1,Bas++;
        }
        while(Q--){
            LL val=read();
            LL len=Find(val);
            LL res=sum[len]-(Bas+1+Bas+len)*(len)/2*val;
            res-=Bas*(Bas+1)/2*val;
            res+=P;
            cout<<res<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！