$\texttt{Kruskal}$ 重构树 + 倍增求 $\texttt{LCA}$ 简单题。

题目链接：LibreOJ 2876/JOISC2014 D2T1。

题目

题目描述

原题 pdf

题意翻译

JOI 君所居住的 IOI 市以一年四季都十分炎热著称。

IOI 市被分成 $H$ 行，每行包含 $W$ 块区域。每个区域都是建筑物、原野、墙壁之一。

IOI 市有 $P$ 个区域是建筑物，坐标分别为 $(A _ 1,B _ 1),(A _ 2,B _ 2),\cdots,(A _ P,B _ P)$。

JOI 君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。

JOI 君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上太阳非常毒辣，因此在原野上每走过一个区域都需要 $1$ 升水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此 IOI 市的市民一般都携带水壶出行。大小为 $x$ 的水壶最多可以装 $x$ 升水，建筑物里有自来水可以将水壶装满。

由于携带大水壶是一件很困难的事情，因此 JOI 君决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。

现在给出 IOI 市的地图和 $Q$ 个询问，第 $i$ 个询问包含两个整数 $S _ i,T _ i$，对于每个询问，请输出：要从建筑物 $S _ i$ 移动到 $T _ i$，至少需要多大的水壶？

数据范围

变量	数据范围
$H,W$	$1\leq H,W\leq 2000$
$P,Q$	$2\leq P,Q\leq 2\times 10^5$

子任务编号	分值	附加条件
$1$	$10$	$H,W,P\leq 200$
$2$	$30$	$P\leq 5000,Q=1$
$3$		$P\leq 5000,Q\leq 10^4$
$4$		无

时空限制

题目编号	时间限制	空间限制
JOISC2014 D2T1	$5\text{s}$	$512\text{MiB}$

题解

思路

先对整张图进行 $\texttt{BFS}$ 染色，每个点的颜色为到它的最近的建筑编号，权值为最近的距离。

对于两个颜色不同的相邻点 $u,v$，我们不妨记录一条边为 $(\text{color} _ u,\text{color} _ v,\text{dis} _ u+\text{dis} _ v)$。

那么我们显然可以发现，城市 $i$ 到 $j$ 的最小水壶就是对应颜色点之间的最短路径。

我们用 $\texttt{Kruskal}$ 重构树维护即可。

注意事项：原图不一定联通，形成的是 $\texttt{Kruskal}$ 重构森林，不要只从一个点开始搜索。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXH=2000+5;
const int MAXW=2000+5;
const int MAXP=200000+5;
const int MAXQ=200000+5;

int H,W,p,q;
char M[MAXH][MAXW];
int a[MAXP],b[MAXP];

struct Node{
    int x,y,d,id;
    inline Node(reg int x=0,reg int y=0,reg int d=0,reg int id=0):x(x),y(y),d(d),id(id){
        return;
    }
};

queue<Node> Q;

inline bool check(reg int x,reg int y){
    return 1<=x&&x<=H&&1<=y&&y<=W&&M[x][y]=='.';
}

bool vis[MAXH][MAXW];
int dis[MAXH][MAXW];
int color[MAXH][MAXW];

inline void BFS(void){
    for(reg int i=1;i<=p;++i){
        vis[a[i]][b[i]]=true;
        dis[a[i]][b[i]]=0;
        color[a[i]][b[i]]=i;
        Q.push(Node(a[i],b[i],0,i));
    }
    while(!Q.empty()){
        static Node t;
        t=Q.front();
        Q.pop();
        reg int x=t.x,y=t.y,d=t.d,id=t.id;
        const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
        for(reg int i=0;i<4;++i){
            reg int fx=x+dx[i],fy=y+dy[i];
            if(check(fx,fy))
                if(!vis[fx][fy]){
                    vis[fx][fy]=true;
                    dis[fx][fy]=d+1;
                    color[fx][fy]=id;
                    Q.push(Node(fx,fy,d+1,id));
                }
        }
    }
    return;
}

struct Edge{
    int from,to,len;
    inline Edge(reg int from=0,reg int to=0,reg int len=0):from(from),to(to),len(len){
        return;
    }
    inline bool operator<(const Edge& a)const{
        return len<a.len;
    }
};

namespace UnionFind{
    int fa[MAXP*2];
    inline void Init(reg int size){
        for(reg int i=1;i<=size;++i)
            fa[i]=i;
        return;
    }
    inline int find(reg int x){
        if(x==fa[x])
            return x;
        else
            return fa[x]=find(fa[x]);
    }
    inline void merge(reg int a,reg int b){
        reg int ra=find(a),rb=find(b);
        if(ra!=rb)
            fa[rb]=ra;
        return;
    }
    inline bool search(reg int a,reg int b){
        return find(a)==find(b);
    }
}

int tot;
const int MAXSIZE=MAXH*MAXW;
Edge E[MAXSIZE];

namespace Tree{
    const int MAXV=MAXP*2;
    int root;
    int cnt,head[MAXV],to[MAXV],Next[MAXV];
    int v[MAXV],inDeg[MAXV];
    inline void Add_Edge(reg int u,reg int v){
        Next[++cnt]=head[u];
        to[cnt]=v;
        head[u]=cnt;
        return;
    }
    const int MAXLOG2V=19+1;
    int fa[MAXV][MAXLOG2V],dep[MAXV];
    inline void DFS(reg int ID,reg int father){
        fa[ID][0]=father;
        dep[ID]=dep[father]+1;
        for(reg int i=1;i<MAXLOG2V;++i)
            fa[ID][i]=fa[fa[ID][i-1]][i-1];
        for(reg int i=head[ID];i;i=Next[i])
            DFS(to[i],ID);
        return;
    }
    inline int LCA(int x,int y){
        if(dep[x]>dep[y])
            swap(x,y);
        for(reg int i=MAXLOG2V-1;i>=0;--i)
            if(dep[fa[y][i]]>=dep[x])
                y=fa[y][i];
        if(x==y)
            return x;
        for(reg int i=MAXLOG2V-1;i>=0;--i)
            if(fa[x][i]!=fa[y][i])
                x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}

inline void Build(void){
    for(reg int i=1;i<=H;++i)
        for(reg int j=1;j<=W;++j)
            if(M[i][j]!='#'){
                const int dx[]={0,1},dy[]={1,0};
                for(reg int k=0;k<2;++k){
                    reg int fx=i+dx[k],fy=j+dy[k];
                    if(check(fx,fy)&&color[i][j]!=color[fx][fy])
                        E[++tot]=Edge(color[i][j],color[fx][fy],dis[i][j]+dis[fx][fy]);
                }
            }
    sort(E+1,E+tot+1);
    using namespace UnionFind;
    Init(2*p);
    reg int pcnt=p;
    for(reg int i=1;i<=tot;++i)
        if(!search(E[i].from,E[i].to)){
            reg int k=++pcnt;
            reg int a=find(E[i].from),b=find(E[i].to);
            Tree::Add_Edge(k,a);
            Tree::Add_Edge(k,b);
            ++Tree::inDeg[a];
            ++Tree::inDeg[b];
            Tree::v[k]=E[i].len;
            merge(k,a),merge(k,b);
        }
    for(reg int i=1;i<=pcnt;++i)
        if(!Tree::inDeg[i])
            Tree::DFS(i,0);
    return;
}

int main(void){
    scanf("%d%d%d%d",&H,&W,&p,&q);
    for(reg int i=1;i<=H;++i)
        scanf("%s",M[i]+1);
    for(reg int i=1;i<=p;++i)
        scanf("%d%d",&a[i],&b[i]);
    BFS();
    Build();
    while(q--){
        static int s,t;
        scanf("%d%d",&s,&t);
        reg int lca=Tree::LCA(s,t);
        if(lca==0)
            puts("-1");
        else{
            reg int ans=Tree::v[lca];
            printf("%d\n",ans);
        }
    }
    return 0;
}