题解 P6765 【[APIO2020]交换城市【暂无数据】】

周子衡 · 2020-08-18 16:42:40 · 题解

前置思想：Kruskal 重构树

在讲解原题的算法前，先简单介绍一下 Kruskal 重构树的思想。一个经典问题：

给一张无向图 G，边有边权。每次询问给定 x,v，求从 x 出发只经过边权 \leq v 的边能到达多少个点。强制在线。

众所周知，图上两点的最小瓶颈路（也就是最大边最小的路）一定包括最小生成树上两点的路。所以我们可以先把边排序，用 Kruskal 算法求出最小生成树。但这样仍然不能方便地求出答案，怎么办呢？Kruskal 重构树的思想是：在 Kruskal 算法确定一条最小生成树上的边 (x,y) 时，不直接连接 (x,y)，而是新建一个节点 T，分别连接 (T,x),(T,y)，将 T 的点权设置为 x,y 的边权，这就形成了 Kruskal 重构树。容易发现一些性质：

对于每个点 x，x 祖先上的点权单调递增。
对于每个点 x 和每个阈值 v，从 x 出发只经过边权 \leq v 的边能到达的点的集合，和 x 祖先节点中深度最大的 \leq v 的节点的子树内的所有原图节点的集合是一样的。这样就可以解决上面的题目了。
对于两点 x,y，x,y 的最小瓶颈边权（也就是最大边最小的路的最大边权）等于 x,y 的最近公共祖先（LCA）的点权。

关于更详细的讲解，请见 NOI2018 归程一题的题解。

对于本题来说，也可以理解为是查询两点间的瓶颈边，我们尝试运用类似 Kruskal 重构树的思想。

首先分析原题中的描述，可以知道：两点 x,y 能互相派出使者访问，当且仅当两点连通，且它们所在的连通块不是一条链。 证明较为简单，连通性显然必须满足，而如果连通块是链也显然无解，尝试一下发现只要有度数 \geq 3 的点或者环那么必定有解。

将边从小到大排序，运行和 Kruskal 算法类似的过程。不同的是，我们不仅要维护连通性，还要维护一个连通块究竟是不是链。发现一条链的性质很大程度上取决于两个端点，于是不妨在并查集的根节点处维护两个数组 st_i,en_i，如果该连通块是链，则存储链的端点。当一个连通块从链变成非链时，我们就在 Kruskal 重构树上新建一个节点，这个节点向所有链上的点连边；连通块合并同理。不难发现这样做仍然能保证原来 Kruskal 重构树的大部分性质，而且也能用 LCA 来处理在线询问。

简单来说，我们扫描每条边：

如果边两端已经连通：如果这个连通块是一条链，那么加上这条边显然不再是链了，那么打上标记，同时在 Kruskal 重构树上连边；否则没有变化。
如果没有连通：
- 如果原来两个连通块有至少一个不是链，那么新连通块也一定不是链；
- 如果原来两个连通块都是链，那么新连通块是不是链取决于连边是不是在端点之间进行的。也可简单维护。

注意我们由于要维护一个点所在的连通块，且要支持合并，应采用启发式合并，使时间复杂度稳定在 O(n\log n)。

总时间复杂度 O((n+q)\log n)。

下面是代码，其中并查集 B 用来维护连通性，conn_i 表示并查集里以 i 为根的连通块是不是脱离链的形态了，tr 表示 Kruskal 重构树的边。

#include"swap.h"

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct BCJ
{
    int fa[500000];
    void init(int n){for(int i=0;i<n;i++)fa[i]=i;}
    int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
}B;

struct e
{
    int u,v,w;e(int uu=0,int vv=0,int ww=0):u(uu),v(vv),w(ww){}
};vector<e> ed;
bool operator<(e a,e b){return a.w<b.w;}

bool conn[500000];int st[500000],en[500000],rt[500000];vector<int> pnt[500000];

vector<int> tr[500000];

int fa[500000][20],dep[500000];

void dfs(int u,int f)
{
    fa[u][0]=f;for(int i=1;i<20;i++)fa[u][i]=fa[u][i-1]==-1?-1:fa[fa[u][i-1]][i-1];
    rt[u]=f==-1?u:rt[f],dep[u]=f==-1?1:dep[f]+1;
    for(int i=0;i<tr[u].size();i++)dfs(tr[u][i],u);
}

int LCA(int x,int y)
{
    if(rt[x]!=rt[y])return -1;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)
    {
        if(fa[x][i]!=-1&&dep[fa[x][i]]>=dep[y])x=fa[x][i];
    }
    if(x==y)return x;
    for(int i=19;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
int n,m;
void init(int N, int M,vector<int> U,vector<int> V,vector<int> W)
{
    n=N,m=M;
    for(int i=0;i<M;i++)ed.push_back(e(U[i],V[i],W[i]));sort(ed.begin(),ed.end());
    B.init(N);for(int i=0;i<N;i++)st[i]=en[i]=rt[i]=i,pnt[i].push_back(i);
    for(int i=0;i<M;i++)
    {
        int u=ed[i].u,v=ed[i].v,fu=B.fnd(u),fv=B.fnd(v);
        if(pnt[fu].size()<pnt[fv].size()){swap(u,v),swap(fu,fv);}
        if(fu==fv)
        {
            if(!conn[fu])
            {
                conn[fu]=1;
                for(int j=0;j<pnt[fu].size();j++)tr[i+N].push_back(pnt[fu][j]);
                rt[fu]=i+N;
            }
        }
        else
        {
            if(conn[fu]||conn[fv])
            {
                if(conn[fu])tr[i+N].push_back(rt[fu]);
                else for(int j=0;j<pnt[fu].size();j++)tr[i+N].push_back(pnt[fu][j]);
                if(conn[fv])tr[i+N].push_back(rt[fv]);
                else for(int j=0;j<pnt[fv].size();j++)tr[i+N].push_back(pnt[fv][j]);
                conn[fu]=1,rt[fu]=i+N;B.fa[fv]=fu;
            }
            else
            {
                if((u==st[fu]||u==en[fu])&&(v==st[fv]||v==en[fv]))
                {
                    st[fu]=u^st[fu]^en[fu];en[fu]=v^st[fv]^en[fv];
                    for(int j=0;j<pnt[fv].size();j++)pnt[fu].push_back(pnt[fv][j]);
                    B.fa[fv]=fu;
                }
                else
                {
                    conn[fu]=1;
                    for(int j=0;j<pnt[fu].size();j++)tr[i+N].push_back(pnt[fu][j]);
                    for(int j=0;j<pnt[fv].size();j++)tr[i+N].push_back(pnt[fv][j]);
                    B.fa[fv]=fu;rt[fu]=i+N;
                }
            }

        }
    }
    /*for(int i=0;i<N+M;i++)
    {
        printf("%d: ",i);
        for(int j=0;j<tr[i].size();j++)printf("%d ",tr[i][j]);puts("");
    }*/
    for(int i=N+M-1;i>=0;i--)
    {
        if(!dep[i])dfs(i,-1);
    }
    //for(int i=0;i<N+M;i++){printf("%d\n",dep[i]);for(int j=0;j<4;j++)printf("%d ",fa[i][j]);puts("");}
}

int getMinimumFuelCapacity(int X,int Y)
{

    int u=LCA(X,Y);if(u==-1)return -1;
    return ed[u-n].w;
}