HT-65-NOI-T2 / LOJ566 题解

KSCD_ · 2025-06-24 21:16:11 · 题解

Upd（26.06.19）：三轮省集出这题，找到原题了。暴力调不过，发现去年写的暴力也挂了，原因是权值相等的边应该看成不等权值，即排序后对每个分界点做一遍。已更新。

题意

设一棵树的权值为 \min_{x}(\sum_i \left|w_i-x\right|)，其中 w_i 为所有边权，x 取任意实数。给定 n 个点 m 条边的无向图，求其最大权值生成树。n\le 2\times {10}^5,m\le 5\times {10}^5。

题解

显然给定 w 后取其中位数为 x 一定最优。考虑枚举边权作为中位数 x，以其为分界点，认为 w\le x 的边为白边，权值为 x-w；其余为黑边，权值为 w-x。此时若 n 为奇数，则两种边各选 \frac{n-1}2 条即可；若 n 为偶数，考虑两种边各选 \lfloor \frac{n-1}2\rfloor 条，即少选一条边，形成两个连通块。由于边权均非负，一定不会超过答案；而枚举到最终答案中位数时，会得到对应生成树去掉中位数边的两个连通块，而该边权值为 0，因此一定可以求出答案。

此时需要解决两种边分别选择 c=\lfloor\frac{n-1}2\rfloor 条的最大生成森林，官解给了一种每次增加一条白边的做法，笔者不会证也没写。事实上目前题意即为 [国家集训队] Tree I，可以使用 wqs 二分求解。具体地，设 f_i 表示 i 条白边的答案，则 (i,f_i) 形成了一个上凸包。证明不太会，感性理解可以从没有白边开始，每次增加一条白边，答案能增多的值不多于上次。从没有黑边开始同理，这两种各能得到四分之一个凸包，因此整体是上凸的。

考虑用斜率为 k 的直线切这个凸包，切到的点 t 随 k 增大而减小。确定 k 后要最大化截距 b=f_i-ki，可以将 -ki 的贡献放到每条白边上，即将白边权值改为 x-w-k，然后用 Kruskal 求最大生成森林，从而得到最大的 b 和对应的白边条数 t。这里可在 b 最大前提下要求白边数量 t 尽可能少，然后二分出 t\le c 的最大 k，该 k 即可切到 (f_c,c) 点，再跑一遍后求 f_c=b+kc 即为答案。对所有中位数取最大值即可，注意要判掉无解情况，时间复杂度 O(m^2\log V\alpha(n))，可以得到 50 分。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
const int P=2e9+1e7;
const ll inf=1e18+1e17;
int n,m,cc,C,cnt,f[N],s[N]; ll res,cur;
struct edg{int u,v; ll w; bool f;}e[N],E[N];
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool mg(int x,int y)
{
    x=finds(x),y=finds(y);
    if(x==y) return false;
    if(s[x]>s[y]) swap(x,y);
    f[x]=y,s[y]+=s[x]; return true;
}
void chk(ll k)
{
    for(int i=1;i<=m;i++) E[i]=e[i],E[i].w-=E[i].f*k;
    sort(E+1,E+1+m,[&](edg A,edg B)->bool {return A.w==B.w?A.f<B.f:A.w>B.w;});
    for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
    cur=cnt=cc=0;
    if(C) for(int i=1;i<=m;i++) if(mg(E[i].u,E[i].v))
    {
        cur+=E[i].w,cnt+=E[i].f,cc++;
        if(cc==C*2) break;
    }
}
ll calc(ll X)
{
    cnt=0;
    for(int i=1;i<=m;i++) e[i].w=(e[i].f?X-e[i].w:e[i].w-X);
    ll l=-P,r=P,rk=P+1,tr;
    while(l<=r)
    {
        ll mid=(l+r)/2; chk(mid);
        if(cnt<=C) rk=mid,r=mid-1;
        else l=mid+1;
    }
    chk(rk-1);
    if(rk>P||cnt<C) tr=-inf;
    else chk(rk),tr=cur+1ll*C*rk;
    for(int i=1;i<=m;i++) e[i].w=(e[i].f?X-e[i].w:e[i].w+X);
    return tr;
}
void sol()
{
    cin>>n>>m,res=-inf,C=(n-1)/2;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w,e[i].f=0;
    sort(e+1,e+1+m,[&](edg A,edg B)->bool {return A.w<B.w;});
    if(m>1000) return;
    for(int i=1;i<=m;i++) e[i].f=1,res=max(res,calc(e[i].w));
    cout<<res<<'\n';
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int TT=1;
    while(TT--) sol();
    return 0;
}

观察上述代码，注意到同时给所有边加上一个值 x 不会改变最终树的形态，即求出的白边条数 t 不变。因此白边边权变为 2x-k-w，黑边边权变为 w。此时 chk 函数的结果只与 X=2x-k 有关，根据上面的凸性可以说明此时 t 随 X 增大而增大，因此可以直接二分 X 求解。

此时要求的问题如下：原图中每条边产生白边 (u,v,X-w) 和黑边 (u,v,w)，求 w\le x 的白边和 w>x 的黑边形成的 2c 条边的最大生成森林。考虑直接在 2m 条边中用 Kruskal 求解，并证明这样做是对的。首先若存在黑边 w_1 和白边 X-w_2，且 w_1<w_2，显然改为黑边 w_2 和 白边 X-w_1 更优，因此跑出的结果一定是 w 上某个前缀为白边，之后为黑边。

此时显然存在一个 x 满足该前缀 w\le x 且之后 w>x，因此这样做是对的。最终答案为 \sum\left|x-w\right|，在黑白边均为 c 条时即为 \sum_{i>x} w_i-\sum_{i\le x}w_i，即跑出的最大生成森林权值和减去 cX，这样就做完了。由于按 X-w 排序只需要将 w 有序的序列翻转，不需要每次 chk 都排序，时间复杂度为 O(m\log V\alpha(n))。

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e5+10;
const int P=1e9+1e7;
const ll inf=1e18+1e17;
int n,m,k,c,a[N],f[N],s[N],C,cx; ll res,ans=-inf;
struct edg{int u,v,w;}e[N],E[N];
bool cmp(edg ta,edg tb) {return ta.w>tb.w;}
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool merg(int x,int y)
{
    x=finds(x),y=finds(y);
    if(x==y) return false;
    s[y]+=s[x],f[x]=y; return true;
}
void add(edg te,bool f)
{
    if(C==c*2) return;
    if(merg(te.u,te.v)) C++,cx+=f,res+=te.w;
}
void chk(ll X)
{
    for(int i=1;i<=m;i++) e[i]=E[m-i+1],e[i].w=X-e[i].w;
    res=0,C=0,cx=0; int pa=1,pb=1;
    for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
    while(pa<=m&&pb<=m)
    {
        if(e[pa].w>E[pb].w) add(e[pa],1),pa++;
        else add(E[pb],0),pb++;
    }
    while(pa<=m) add(e[pa],1),pa++;
    while(pb<=m) add(E[pb],0),pb++;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m,c=((n-1)>>1);
    for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
    sort(E+1,E+1+m,cmp);
    ll l=-P,r=2*P,rk=-P-1;
    while(l<=r)
    {
        ll mid=((l+r)>>1); chk(mid);
        if(cx<=c) rk=mid,l=mid+1;
        else r=mid-1;
    }
    chk(rk),cout<<res-c*rk;
    return 0;
}