【ds 记录】P9701 [GDCPC2023] Classic Problem

IdnadRev · 2023-10-04 11:19:38 · 题解

我们先将值域离散成至多 4m+1 段，每一段要么没有边相连，要么是一个单点。由于第一类一定内部使用长为 1 的边相连，因此开始时我们仅有 4m+1 个连通块。

使用 Boruvka，每一轮需要找到每一连通块的最小出边，我们分两类边讨论：

• 最小修改过的出边：暴力枚举相连的边，检查是否连接不同连通块。
• 最小未修改的出边：分在这一段前/后讨论，由于对称性不妨只考虑前者。我们暴力向前枚举不同连通块的段（可以记录前面第一个与其不同连通块的段来帮助枚举，具体可见 std），并判断是否有边相连，若有则继续往前枚举，由于边数总和是 O(m)，无效的枚举数量也是 O(m) 级别。

于是经过 O(\log m) 轮后我们能得到最小生成树，复杂度 O(m\log m)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=400005;
int n,m,T,nums,tot,stp;
long long ans;
int num[maxn],xx[maxn],yy[maxn],zz[maxn],typ[maxn],dsu[maxn],rec[maxn],mn[maxn],id[maxn],ll[maxn],rr[maxn],vis[maxn],pre[maxn],suf[maxn];
vector<int>v[maxn];
int find(int x){
    return dsu[x]==x? x:dsu[x]=find(dsu[x]);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m),nums=tot=ans=0;
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&xx[i],&yy[i],&zz[i]),num[++nums]=xx[i],num[++nums]=yy[i];
        sort(num+1,num+1+nums),nums=unique(num+1,num+1+nums)-num-1;
        int lst=0;
        for(int i=1;i<=nums;i++){
            if(num[i]>lst+1)
                tot++,ll[tot]=lst+1,rr[tot]=num[i]-1,typ[tot]=0;
            tot++,ll[tot]=num[i],rr[tot]=num[i],typ[tot]=i,id[i]=tot;
            lst=num[i];
        }
        for(int i=1;i<=m;i++){
            xx[i]=lower_bound(num+1,num+1+nums,xx[i])-num;
            yy[i]=lower_bound(num+1,num+1+nums,yy[i])-num;
            v[xx[i]].emplace_back(i),v[yy[i]].emplace_back(i);
        }
        if(lst+1<=n)
            tot++,ll[tot]=lst+1,rr[tot]=n,typ[tot]=0;
        for(int i=1;i<=tot;i++)
            ans+=rr[i]-ll[i],dsu[i]=i;
        int cnt=0;
        while(cnt<tot-1){
            for(int i=1;i<=tot;i++)
                if(dsu[i]==i)
                    mn[i]=2e9,rec[i]=-1;
            for(int i=1;i<=tot;i++)
                if(typ[i]){
                    int x=typ[i];
                    for(int j=0;j<v[x].size();j++){
                        int k=v[x][j],y=id[xx[k]+yy[k]-x];
                        if(find(y)!=find(i)&&mn[find(i)]>zz[k])
                            mn[find(i)]=zz[k],rec[find(i)]=find(y);
                    }
                }
            pre[1]=0;
            for(int i=2;i<=tot;i++){
                if(find(i-1)==find(i))
                    pre[i]=pre[i-1];
                else pre[i]=i-1;
            }
            suf[tot]=tot+1;
            for(int i=tot-1;i>=1;i--){
                if(find(i+1)==find(i))
                    suf[i]=suf[i+1];
                else suf[i]=i+1;
            }
            for(int i=1;i<=tot;i++){
                stp++;
                if(typ[i]){
                    int x=typ[i];
                    for(int j=0;j<v[x].size();j++){
                        int k=v[x][j];
                        vis[id[xx[k]+yy[k]-x]]=stp;
                    }
                }
                int j=i;
                while(j){
                    if(find(j)==find(i))
                        j=pre[j];
                    else if(vis[j]==stp)
                        j--;
                    else{
                        int c=ll[i]-rr[j];
                        if(mn[find(i)]>c)
                            mn[find(i)]=c,rec[find(i)]=find(j);
                        break;
                    }
                }
                j=i;
                while(j<=tot){
                    if(find(j)==find(i))
                        j=suf[j];
                    else if(vis[j]==stp)
                        j++;
                    else{
                        int c=ll[j]-rr[i];
                        if(mn[find(i)]>c)
                            mn[find(i)]=c,rec[find(i)]=find(j);
                        break;
                    }
                }
            }
            for(int i=1;i<=tot;i++)
                if(dsu[i]==i&&rec[i]!=-1&&i!=find(rec[i]))
                    cnt++,ans+=mn[i],dsu[i]=find(rec[i]);
        }
        printf("%lld\n",ans);
        for(int i=1;i<=tot;i++)
            v[i].clear();
    }
    return 0;
}