题解 CF1648E【Air Reform】

· · 题解

portal

首先原图中最短路是“最大值最小”的描述，那么自然想到 Kruskal 重构树。则两点间的最短路为其在 Kruskal 重构树上的 LCA 的权值。

那么考虑补图。显然我们也要把补图的 Kruskal 重构树建出来。

但是我们显然无法在补图上执行 Kruskal 算法——因为边数是 O(n^2) 的。

怎么办呢？我们发现，可以先求出补图的 最小生成树，然后根据最小生成树可以简单求出 Kruskal 重构树。

但是最小生成树应该怎么求呢？

答案不是 Prim 或 Kruskal 这两种常见的算法，而是 未曾设想的道路 Boruvka 算法。

Boruvka 算法是维护若干连通块的过程。

其会执行若干轮。在每一轮中，从每个连通块出发找到其与任一其它连通块间 边权最小的边。然后，连接这所有的边（只要其两个端点不位于同一连通块中）。

重复执行，直到仅剩一个连通块。

  • 正确性证明：每个连通块要与其它连通块连通，显然经由该最小边权边是最优的。

    假如出现了环，则显然环上每条边的边权都相等且最小（不然就不会成环）。那么就扔掉一条边，用剩下的边连成一个大连通块即可。

  • 复杂度证明：每轮中，每个连通块必然与另一个连通块合并。故每轮会让连通块数量减半，至多执行 \log n 轮。

可以发现，Boruvka 算法并不要求求出每条边的边权，只要你能够对于每个点求出其与不在同一个连通块中的点间的最小边权即可。

考虑本题。我们考虑二分一个点 x 在 Kruskal 重构树上的祖先，并且判定这个祖先是否可以作为从这个点出发的连边。

考虑判定条件。

其中第二条限制较易遗忘，这是因为 补图 中不存在原图中有的边。

那么考虑如何判定。我们事实上可以不使用二分，而是找到在 Kruskal 重构树的 dfs 序上，在 x 之前/之后且满足上述条件的首个点，然后找到二者 LCA 的较深者，即为我们需要的点。

考虑对之前之后各维护一个指针。显然随着 Boruvka 算法的执行，之前的指针会不断前移，之后的指针会不断后移。

那么我们用数据结构维护每个连通块，然后每次在数据结构中找到指针之后下一个不在数据结构中的点，假如这个点对应的边出现在原图中就再次寻找即可。可以发现失配的总次数是 O(m) 级别的。

考虑用什么数据结构维护。事实上，只需每轮都重构连通块即可——因为一共仅执行 O(\log n) 轮。暴力维护连续的来自同一连通块的段，然后查询后继之类就直接跳即可。可以发现这样可以做到线性查询。

复杂度对数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200100;
int T,n,E,cnt,ord[N],dsu[N<<1],val[N<<1];
struct EDGE{int x,y,z;};
vector<int>v[N],u[N<<1];
vector<int>::iterator itf[N],itb[N];
inline int find(const int&x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
int dfn[N<<1],rev[N<<1],tot,lim,dep[N<<1],st[20][N<<2],LG[N<<2],fir[N<<1];
inline int MIN(const int&x,const int&y){return dep[x]<dep[y]?x:y;}
inline bool dfncmp(const int&x,const int&y){return dfn[x]<dfn[y];}
inline int LCA(int x,int y){
    x=fir[x],y=fir[y];if(x>y)swap(x,y);
    int k=LG[y-x+1];
    return MIN(st[k][x],st[k][y-(1<<k)+1]);
}
void dfs(int x){
    if(x<=n)dfn[x]=++tot,rev[tot]=x;
    st[0][++lim]=x,fir[x]=lim;
    for(auto y:u[x])dep[y]=dep[x]+1,dfs(y),st[0][++lim]=x;
}
void Kruskal(EDGE*e,int m){
    cnt=n,tot=lim=0;
    for(int i=1;i<=m;i++)ord[i]=i;
    sort(ord+1,ord+m+1,[&](int x,int y){return e[x].z<e[y].z;});
    for(int i=1;i<=n;i++)dsu[i]=i;
    for(int i=1,x,y,z;i<=m;i++)
        if((x=find(e[ord[i]].x))!=(y=find(e[ord[i]].y)))
        val[z=++cnt]=e[ord[i]].z,
        u[z].push_back(x),u[z].push_back(y),
        dsu[x]=dsu[y]=dsu[z]=z;
    dfs(cnt);
    for(int i=2;i<=lim;i++)LG[i]=LG[i>>1]+1;
    for(int j=1;j<=LG[lim];j++)for(int i=1;i+(1<<j)-1<=lim;i++)
        st[j][i]=MIN(st[j-1][i],st[j-1][i+(1<<j-1)]);
    for(int i=1;i<=cnt;i++)u[i].clear();
}
int lp[N],rp[N];
int fp[N],bp[N];
int mn[N],mx[N],my[N],m;
EDGE e[N],f[N];
void mina(){
    scanf("%d%d",&n,&m),E=0;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z),
        v[e[i].x].push_back(e[i].y),v[e[i].y].push_back(e[i].x);
    Kruskal(e,m);
    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end(),dfncmp);
        itf[i]=itb[i]=lower_bound(v[i].begin(),v[i].end(),i,dfncmp);
        if(itf[i]!=v[i].begin())itf[i]--;
        fp[i]=bp[i]=dfn[i];
    }
    for(int i=1;i<=n;i++)dsu[i]=i;
    while(E<n-1){
        for(int l=1,r=1;l<=n;l=r){
            for(r=l;r<=n&&find(rev[l])==find(rev[r]);r++);
            for(int i=l;i<r;i++)lp[i]=l,rp[i]=r-1;
        }
        for(int i=1;i<=n;i++)mn[i]=0x3f3f3f3f,mx[i]=my[i]=-1;
//      for(int i=1;i<=n;i++)printf("[%d,%d]",lp[i],rp[i]);puts("");
        for(int i=1;i<=n;i++){
            while(fp[i]){
                if(find(rev[fp[i]])==find(i)){fp[i]=lp[fp[i]]-1;continue;}
                while(itf[i]!=v[i].begin()&&dfn[*itf[i]]>fp[i])itf[i]--;
                if(dfn[*itf[i]]==fp[i])fp[i]--;
                else break;
            }
            while(bp[i]<=n){
                if(find(rev[bp[i]])==find(i)){bp[i]=rp[bp[i]]+1;continue;}
                while(itb[i]!=v[i].end()&&dfn[*itb[i]]<bp[i])itb[i]++;
                if(itb[i]!=v[i].end()&&dfn[*itb[i]]==bp[i])bp[i]++;
                else break;
            }
            int z=0x3f3f3f3f,y=-1;
            if(fp[i]){
                int Z=val[LCA(rev[fp[i]],i)];
                if(Z<z)z=Z,y=rev[fp[i]];
            }
            if(bp[i]<=n){
                int Z=val[LCA(i,rev[bp[i]])];
                if(Z<z)z=Z,y=rev[bp[i]];
            }
            if(z<mn[find(i)])mn[find(i)]=z,mx[find(i)]=i,my[find(i)]=y;
        }
        for(int i=1;i<=n;i++)if(dsu[i]==i){
            int j=find(my[i]);
            if(j==i)continue;
//          printf("LINK:%d,%d:%d\n",mx[i],my[i],mn[i]);
            dsu[i]=j;
            ++E,f[E].x=mx[i],f[E].y=my[i],f[E].z=mn[i];
        }
    }
    Kruskal(f,E);
    for(int i=1;i<=m;i++)printf("%d ",val[LCA(e[i].x,e[i].y)]);puts("");
    for(int i=1;i<=n;i++)v[i].clear();
}
int main(){
    scanf("%d",&T);
    while(T--)mina();
    return 0;
}