P9701

Albert_van · 2023-11-07 20:22:37 · 题解

Boruvka 蓝莓算法模板题。

首先图的规模太大，考虑压缩一些点或状态。m 条指定边只涉及 2m 个结点，称它们为关键点，那么相邻关键点 l 与 r 间所有点的连边没有限制。于是在整个图的 MST 中，必然有一条长 r-l-2 的链贯穿 [l+1,r-1] 间所有非关键点。

要证明，考虑利用 MST 的性质：x 到 y 在树上路径最大值，等于原图路径最大值的最小值。这里对 x,y\in(l,r) 有 x 到 y 路径最大值为 1。因为 x 和 y 连向外界的边权不会小于 1，所以连成链必然不劣。

于是先令答案加上 r-l-2，然后将 [l+1,r-1] 串起来视作一个结点，与关键点一起加入图中。这样点数就降到了 \mathcal O(m) 级别。

对这个新的完全图，使用蓝莓算法求 MST，每轮需对每个点求出离开连通块的最小边。对于指定的关键点间连边，逐个用边权更新两端点即可。考虑剩下边权为两点距离的连边。

初始每个点独立组成连通块时，可以从点 i 出发暴力向前/后跳（p\gets p\mp 1），找到离 i 最近的 p 满足 i 与 p 间没有指定边。这个过程显然花费 \mathcal O(m)。

在一个连通块有多个点时，p 必须同时满足 p 与 i 不在同一块内，复杂度无法保证。进行优化，记录 \operatorname{pre}_p 表示 p 之前第一个不在 p 的连通块内的点，\operatorname{nxt}_p 同理。那么遇到 p 与 i 在同一块内时，令 p\gets \operatorname{pre}_p/\operatorname{nxt}_p 即可。每次这样的操作后，要么 p 合法并结束，要么进行一次 p\gets p\mp 1 的操作，所以这里的花费也是 \mathcal O(m)。

于是每一轮 \mathcal O(m)，总复杂度 \mathcal O(m\log m)。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

const int N=514114;

namespace U{
    int anc[N];
    void set(int n){for(int i=1;i<=n;++i) anc[i]=i;}
    int fnd(int x){return anc[x]==x?x:anc[x]=fnd(anc[x]);}
    void mrg(int x,int y){anc[fnd(x)]=fnd(y);}
}using namespace U;

struct point{int p,id;}pt[N];

struct ed{
    int v,w;
    bool operator<(const ed t)const{return v<t.v;}
};
vector<ed> vc[N];

bool ex(int x,int y){
    auto p=lower_bound(vc[x].begin(),vc[x].end(),(ed){y,0});
    return p!=vc[x].end()&&p->v==y;
}

struct edg{int x,y,w;}e[N];

void upe(edg &k,edg n){if(n.w<k.w) k=n;}

map<int,int> pos;

int u[N],v[N],we[N],l[N],r[N],pre[N],nxt[N];

int main()
{
    int T;scanf("%d",&T);while(T--){
        int n,m;scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",u+i,v+i,we+i);if(u[i]<v[i]) swap(u[i],v[i]);
            pt[i*2-1]=(point){u[i],i};pt[i*2]=(point){v[i],0};
        }
        sort(pt+1,pt+(m<<1|1),[](point x,point y){return x.p<y.p;});
        long long ans=0;int c=0;
        for(int i=1;i<=m<<1;++i){
            int pl=pt[i-1].p,pr=pt[i].p;
            if(pr>pl+1) ans+=pr-pl-2,++c,l[c]=pl+1,r[c]=pr-1;
            if(pr>pl) ++c,l[c]=r[c]=pr;
            pos[pr]=c;int x=pt[i].id;
            if(x) vc[c].push_back((ed){pos[v[x]],we[x]}),vc[pos[v[x]]].push_back((ed){c,we[x]});
        }
        if(pt[m<<1].p<n) ++c,l[c]=pt[m<<1].p+1,r[c]=n,ans+=n-l[c];
        set(n=c);for(int i=1;i<=n;++i) sort(vc[i].begin(),vc[i].end());
        nxt[n+1]=anc[n+1]=0;int kc=n;while(kc>1){
            for(int i=1;i<=n;++i) if(fnd(i)==i) e[i].w=1e9+7;
            for(int i=1;i<=n;++i) pre[i]=fnd(i)==fnd(i-1)?pre[i-1]:i-1;
            for(int i=n;i;--i) nxt[i]=fnd(i)==fnd(i+1)?nxt[i+1]:i+1;
            for(int i=1;i<=n;++i){
                int p=i,a=fnd(i);
                while(fnd(p)==a||ex(i,p)) p=fnd(p)==a?pre[p]:p-1;
                if(p) upe(e[a],(edg){i,p,l[i]-r[p]});
                p=i;while(fnd(p)==a||ex(i,p)) p=fnd(p)==a?nxt[p]:p+1;
                if(p<=n) upe(e[a],(edg){i,p,l[p]-r[i]});
            }
            for(int i=1;i<=n;++i) for(auto[v,w]:vc[i]) if(fnd(i)!=fnd(v))
                upe(e[fnd(i)],(edg){i,v,w});
            for(int i=1;i<=n;++i) if(fnd(i)==i&&fnd(e[i].x)!=fnd(e[i].y))
                U::mrg(e[i].x,e[i].y),ans+=e[i].w,--kc;
        }
        printf("%lld\n",ans);
        for(int i=1;i<=n;++i) vc[i].clear();
    }
}