P6765 [APIO2020] 交换城市

P6765 [APIO2020] 交换城市

来点简单做法，好想好写，不用 Kruskal 重构树！

尽管是 \(O(q\log m\log n)\)，但是实测很快！

考虑只有一次询问，我们可以边做 Kruskal，边实时判断加入一条边以后是否可以建立关系。

首先，一个连通块之内的任意两个点一定都可以或都不可以建立关系。我们称一个内部点可以互相建立关系的连通块为好的连通块。一个好的连通块等价于连通块不为链。

我们定义 \(b_i\) 表示以 \(i\) 为祖先的连通块最早的变成好的连通块的时间，有三种情况会更改 \(b_i\)：

• 和另一个好的连通块相连了。

• 在连通块内又加入了一条边。

• 有一个点度数大于 \(2\)。

这个东西是好处理的。查询时每次只需要判断两个点是否在同一个好的连通块内即可。

inline void link(int u,int v,int i)
{
    ++d[u],++d[v];int fau=find(u),fav=find(v);
    if(fau==fav){if(!b[fau]) b[fau]=i;return ;}//存在环了
    if(!b[fau]&&b[fav]) b[fau]=i;//与好的连通块相连了
    if(b[fau]&&!b[fav]) b[fav]=i;//与好的连通块相连了
    if(siz[fau]>siz[fav]) swap(u,v),swap(fau,fav);//按秩合并
    tim[fau]=i,fa[fau]=fav,siz[fav]+=siz[fau];
    if((d[u]>2||d[v]>2)&&!b[fav]) b[fav]=i;//有点度数大于 2 了
}

对于多次询问，我们肯定不能直接做，所以考虑二分答案。但这样就要求我们记录下每次加入边后的并查集数组。

一个 naive 的想法是用主席树维护，并查集还要按秩合并，再加一个二分，然后直逼三 \(\log\)。

后来发现既然都按秩合并了，干脆不路径压缩，这样每个 \(fa_i\) 只会更改一次，记录一下更改的时间，这样查询历史版本的父亲时，只需要判断是在更改前还是更改后就行了，这样就是双 \(\log\) 了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=1e5+10,MAXM=2e5+10;
int n,m,fa[MAXN],tim[MAXN],siz[MAXN],d[MAXN],b[MAXN];
struct node{int u,v,w;}p[MAXM];
inline int F(int x,int i){return (!tim[x]||i<tim[x])?x:fa[x];}
inline bool cmp(node x,node y){return x.w<y.w;}
inline int find(int x){return (fa[x]==x)?x:find(fa[x]);}
inline void link(int u,int v,int i)
{
    ++d[u],++d[v];int fau=find(u),fav=find(v);
    if(fau==fav){if(!b[fau]) b[fau]=i;return ;}
    if(!b[fau]&&b[fav]) b[fau]=i;
    if(b[fau]&&!b[fav]) b[fav]=i;
    if(siz[fau]>siz[fav]) swap(u,v),swap(fau,fav);
    tim[fau]=i,fa[fau]=fav,siz[fav]+=siz[fau];
    if((d[u]>2||d[v]>2)&&!b[fav]) b[fav]=i;
}
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) p[i+1]={u[i]+1,v[i]+1,w[i]};
    sort(p+1,p+1+m,cmp);
    for(int i=1;i<=n;++i) fa[i]=i,siz[i]=1;
    for(int i=1;i<=m;++i) link(p[i].u,p[i].v,i);
}
inline bool Check(int x,int y,int i)
{
    for(int fa=F(x,i);fa!=x;) x=fa,fa=F(x,i);
    for(int fa=F(y,i);fa!=y;) y=fa,fa=F(y,i);
    return (x==y&&b[x]&&b[x]<=i);
}
int getMinimumFuelCapacity(int x,int y)
{
    ++x,++y;int l=1,r=m;
    if(!Check(x,y,m)) return -1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        Check(x,y,mid)?r=mid:l=mid+1;
    }return p[l].w;
}

顺便提一嘴，如果允许离线的话可以一起二分，\(\log\) 层每次都从头跑一遍 Kruskal，这样并查集可以路径压缩，把并查集复杂度忽略的话就到单 \(\log\) 了。虽然本来就有单 \(\log\) 在线做法。