题目跳转：P14422 [JOISC 2014] 水壶 / Water Bottle

题面简述

给定一个 $H$ 行 $W$ 列的存在障碍的矩形地图。

地图上有 $P$ 个点，每两个点之间的边边权为两点之间最短路径。

$Q$ 次询问点 $S$ 到点 $T$ 之间可能的最大边权最小值。

思路解析

挺有意思的一道题。

刚开始看到这道题的时候不难想到 kruskal 重构树。但是当你思考建边时会发现暴力建边的话时间复杂度 $\Theta(P^2)$，然后就 TLE 了。

于是考虑多源 bfs 建边。当两个点的拓展区域出现重叠时，将这两个点建边，边权为两点的拓展距离之和，时间复杂度 $\Theta(H \times W)$。

然后就是标准的考入斯卡拉 kruskal 重构树了。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
const int L=5005,N=800005;
int tot,h,w,n,q,dep[N],p[L][L],k[N],kfa[N][40],fa[N],dis[L][L],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char g[L][L];
struct node{
	int x,y;
};
queue<node> qp;
struct edge{
	int u,v,w;
	bool operator<(const edge &a)const{
		return w>a.w;
	}
};
priority_queue<edge> qe;
vector<int> son[N];
void bfs(){
	while(!qp.empty()){
		int x=qp.front().x,y=qp.front().y;
		qp.pop();
		for(int i=0;i<=3;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(g[nx][ny]=='#'||nx<1||nx>h||ny<1||ny>w){
				continue;
			}
			if(!p[nx][ny]){
				p[nx][ny]=p[x][y];
				dis[nx][ny]=dis[x][y]+1;
				qp.push({nx,ny});
			}
			else if(p[x][y]<p[nx][ny]){
				qe.push({p[x][y],p[nx][ny],dis[x][y]+dis[nx][ny]});
			}
		}
	}
}
int gro(int x){
	return fa[x]==x?x:fa[x]=gro(fa[x]);
}
void kruskal(){
	while(!qe.empty()){
		int u=qe.top().u,v=qe.top().v,w=qe.top().w;
		qe.pop();
		int f1=gro(u),f2=gro(v);
		if(f1!=f2){
			fa[f1]=fa[f2]=++tot;
			k[tot]=w;
			son[tot].push_back(f1);
			son[tot].push_back(f2);
		}
	}
}
void dfs(int now,int fno){
	kfa[now][0]=fno;
	dep[now]=dep[fno]+1;
	for(int i=1;i<=20;i++){
		kfa[now][i]=kfa[kfa[now][i-1]][i-1];
	}
	for(int i=0;i<son[now].size();i++){
		dfs(son[now][i],now);
	}
}
void calc(int u,int v){
	if(gro(u)!=gro(v)){
		cout<<-1<<"\n";
		return;
	}
	if(dep[u]>dep[v]){
		swap(u,v);
	}
	int tmp=dep[v]-dep[u];
	for(int i=0;tmp;i++){
		if(tmp%2){
			v=kfa[v][i];
		}
		tmp/=2;
	}
	for(int i=20;i>=0&&u!=v;i--){
		if(kfa[u][i]!=kfa[v][i]){
			u=kfa[u][i];
			v=kfa[v][i];
		}
	}
	cout<<k[kfa[u][0]]<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>h>>w>>n>>q;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>g[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		qp.push({x,y});
		p[x][y]=i;
	}
	for(int i=1;i<N;i++){
		fa[i]=i;
	}
	tot=n;
	bfs();
	kruskal();
	for(int i=1;i<=tot;i++){
		if(fa[i]==i){
			dfs(i,0);
		}
	}
	for(int i=1;i<=q;i++){
		int s,t;
		cin>>s>>t;
		calc(s,t);
	}
	return 0;
}