题解：P13548 [OOI 2022] Air Reform

· · 题解

神仙题。

先转化一步题意：我们需要求 S8 Airlines 的航班网络的最小生成树，然后剩下的问题就是一个树上路径查询的问题，倍增即可。

但是 S8 Airlines 的航班网络可能会有很多的边，我们该怎么办？

可以尝试先用 Kruskal 求出 Berlaflot 的航班网络的最小生成树。

我们发现在 Kruskal 的过程中，假设这条边是 u 到 v 的，边权为 w，那么会在 u 所在连通块到 v 所在连通块在原图上没有边的两点之间都连接一条长度为 w 的边。

而对 Berlaflot 的航班网络做 Kruskal 的过程中，w 是单调不降的，也就是我们可以在这同时可以尝试直接对 S8 Airlines 的航班网络做 Kruskal。

设合并时 u 在 Berlaflot 上的最小生成树的连通块是 S_u，v 的为 S_v。

其实我们可以尝试每次对 S_u 的点对应的 S8 Airlines 的航班网络上的所有连通块与 S_v 的点对应的 S8 Airlines 的航班网络上的所有连通块尝试合并。（这句话有点绕，尝试理解一下）

此时我们其实可以枚举每个点暴力合并，为什么？

对于每个连通块枚举点对的时候：

  1. 如果枚举到一个在原图上存在直接连接的边的点对，因为接下来 S_u 和 S_v 将会被合并在一起，所以接下来不会遍历到这条边了，所以这部分时间复杂度是 O(m) 的。

  2. 如果枚举到一个在原图上不存在直接连接的边的点对，那么太棒了可以直接合并了！！！合并次数是 n-1 次的，所以对于这部分的总时间复杂度也是 O(n) 的。

我们现在可以用 vector 套 vector 的数组维护，第一层 vector 表示每个在 S8 Airlines 上的连通块，第二层表 vector 示每个连通块的点。

而数组的下标 u 就表示的整个连通块数组里的点在做 Berlaflot 的 Kruskal 时的并查集的根是 u。（相当于这个集合是 S_u）

注意每次合并完 S_u 和 S_v，需要遍历两个数组，通过用 swap 函数把没有点的连通块换到后面，再通过 vector 的 pop_back 函数删除。（这样做的原因是为了防止这一部分的运行次数计算涉及到第二层 vector 里的点，这样时间复杂度就假了）

很不错，然后可以通过启发式合并来随便合并，这个题就做完了！

注意，你还需要用到并查集来防止在做 Berlaflot 的 Kruskal 时单对 u 和 v 的合并时在连通块间形成环。

并且你需要等到所有第二层 vector 里的连通块合并完了之后再去更改连通块的数组，边遍历处理合并边修改显然是错的。

合并第二层 vector 里的连通块的启发式合并中时，因为有多次合并，所以注意你究竟要合并哪两个连通块。

然后合并 S_u 和 S_v 时，必须用所有点的大小合并，因为 push_back 一个 vector 的时间复杂度是那个 vector 的长度。

能说的就那么多了，给代码，你们自己看着调吧。

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
    int u,v,w;
}e[200010];
inline bool operator < (node x,node y){
    return x.w<y.w;
}
inline bool operator > (node x,node y){
    return x.w>y.w;
}
int fa[200010];
inline int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
unordered_map<int,int>mp[200010];
vector<vector<int> >s[200010];
int siz[200010];
vector<int>E[200010],val[200010];
int F[200010][19],mx[200010][19],dep[200010];
bool vis[200010];
inline void dfs(int x,int fa){
    vis[x]=1;
    F[x][0]=fa,dep[x]=dep[fa]+1;
    for(int i=0;i<E[x].size();i++){
        if(E[x][i]==fa || vis[E[x][i]]) continue;
        dfs(E[x][i],x),mx[E[x][i]][0]=val[x][i];
    }
}
int U[200010],V[200010];
inline int ask(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    int d=dep[x]-dep[y],ans=-2e9;
    for(int k=18;k>=0;k--) if(d&(1<<k)) ans=max(ans,mx[x][k]),x=F[x][k];
    if(x==y) return ans;
    for(int k=18;k>=0;k--) if(F[x][k]!=F[y][k]) ans=max(ans,max(mx[x][k],mx[y][k])),x=F[x][k],y=F[y][k];
    return max(ans,max(mx[x][0],mx[y][0]));
}
int FFF[400010];
inline int Find(int x){
    if(x==FFF[x]) return x;
    return FFF[x]=Find(FFF[x]);
}
int CNT=0;
inline void Air_Reform(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        vector<int>t;
        t.push_back(i);
        fa[i]=i,s[i].clear(),s[i].push_back(t),mp[i].clear(),E[i].clear(),val[i].clear(),siz[i]=1,vis[i]=0;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w,U[i]=u,V[i]=v;
        e[i]=(node){u,v,w},mp[u][v]=mp[v][u]=w;
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        int x=find(e[i].u),y=find(e[i].v),w=e[i].w;
        if(x==y) continue;
        vector<pair<int,int> >mgtsk;//合并任务 
        for(int i=0;i<s[x].size();i++){
            for(int j=0;j<s[y].size();j++){
                bool flag=0;
                if(!FFF[i+1]) FFF[i+1]=i+1;
                if(!FFF[j+n+1]) FFF[j+n+1]=j+n+1;
                if(Find(i+1)==Find(j+n+1)) continue;
                for(int t=0;t<s[x][i].size() && !flag;t++){
                    for(int k=0;k<s[y][j].size() && !flag;k++){
                        if(!mp[s[x][i][t]][s[y][j][k]]){
                            flag=1;
                            E[s[x][i][t]].push_back(s[y][j][k]),val[s[x][i][t]].push_back(w);
                            E[s[y][j][k]].push_back(s[x][i][t]),val[s[y][j][k]].push_back(w);
                        }
                    }
                }
                if(flag){
                    if(!FFF[i+1]) FFF[i+1]=i+1;
                    if(!FFF[j+n+1]) FFF[j+n+1]=j+n+1;
                    FFF[Find(i+1)]=Find(j+n+1);
                    mgtsk.push_back({i,j});
                }
            }
        }
        for(int i=0;i<s[x].size();i++) FFF[i+1]=0;
        for(int j=0;j<s[y].size();j++) FFF[j+n+1]=0;
        for(int i=0;i<mgtsk.size();i++) FFF[mgtsk[i].first]=mgtsk[i].first,FFF[mgtsk[i].second+n+1]=mgtsk[i].second+n+1;
        for(int i=0;i<mgtsk.size();i++){
            int u=Find(mgtsk[i].first),v=Find(mgtsk[i].second+n+1);
            vector<int>&a=((u<=n) ? s[x][u] : s[y][u-n-1]),&b=((v<=n) ? s[x][v] : s[y][v-n-1]);
            if(a.size()<b.size()){
                for(int j=0;j<a.size();j++) b.push_back(a[j]);
                a.clear(),FFF[u]=v;
            }
            else{
                for(int j=0;j<b.size();j++) a.push_back(b[j]);
                b.clear(),FFF[v]=u;
            }
        } 
        for(int i=0;i<mgtsk.size();i++) FFF[mgtsk[i].first]=FFF[mgtsk[i].second+n+1]=0;
        int j=0;
        for(int i=0;i<s[x].size();i++) if(!s[x][i].empty()) swap(s[x][i],s[x][j++]);
        j=0;
        for(int i=0;i<s[y].size();i++) if(!s[y][i].empty()) swap(s[y][i],s[y][j++]);
        while(!s[x].empty() && s[x].back().empty()) s[x].pop_back();
        while(!s[y].empty() && s[y].back().empty()) s[y].pop_back();
        if(siz[x]<siz[y]){
            siz[y]+=siz[x],fa[x]=y;
            for(int i=0;i<s[x].size();i++) s[y].push_back(s[x][i]),s[x][i].clear(); 
            s[x].clear();
        }
        else{
            siz[x]+=siz[y],fa[y]=x;
            for(int i=0;i<s[y].size();i++) s[x].push_back(s[y][i]),s[y][i].clear(); 
            s[y].clear();
        }
    }
    dfs(1,0);
    for(int k=1;k<19;k++) for(int i=1;i<=n;i++) F[i][k]=F[F[i][k-1]][k-1],mx[i][k]=max(mx[i][k-1],mx[F[i][k-1]][k-1]);
    for(int i=1;i<=m;i++) cout<<ask(U[i],V[i])<<" ";
    cout<<"\n";
} 
signed main() {int c,t;cin>>t>>c;while(t--) Air_Reform();}