非常好的一道图论问题.
显然，我们要求城市间的最小生成树，然后查询路径最大值.
然后我们有一个非常神的处理方法：进行多源 BFS，处理出每一个城市的管辖范围.
显然，如果两个城市的管辖范围没有交集的话连边一定不是优秀的（一定会有一种都在管辖范围之内的连边方式来代替这种连边方式）
然后由于每一个点只属于一个城市的管辖范围，所以每个点只会扩展一次，这个 BFS 的复杂度是线性的.
code:
#include <bits/stdc++.h>
#define N 2006
#define M 200005
#define ll long long
using namespace std;
namespace IO {
void setIO(string s) {
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
// freopen(out.c_str(),"w",stdout);
}
};
char str[N];
int n,m,P,Q,edges;
int dep[M];
int hd[M],to[M<<1],nex[M<<1],val[M<<1],vis[M],fa[18][M],Max[18][M];
int wall[N][N],id[N][N],dis[N][N],bel[N][N],p[N*N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
struct node {
int x,y;
node(int x=0,int y=0):x(x),y(y){}
};
struct edge {
int x,y;
edge(int x=0,int y=0):x(x),y(y){}
};
queue<node>q;
vector<edge>G[N*N];
void add(int u,int v,int c) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;
}
void init() {
for(int i=0;i<N*N;++i) p[i]=i;
}
int find(int x) {
return p[x]==x?x:p[x]=find(p[x]);
}
int merge(int x,int y) {
x=find(x);
y=find(y);
if(x==y)
return 0;
p[x]=y;
return 1;
}
void dfs(int x,int ff) {
vis[x]=1;
fa[0][x]=ff;
dep[x]=dep[ff]+1;
for(int i=1;i<18;++i)
fa[i][x]=fa[i-1][fa[i-1][x]];
for(int i=1;i<18;++i)
Max[i][x]=max(Max[i-1][fa[i-1][x]],Max[i-1][x]);
for(int i=hd[x];i;i=nex[i]) {
int v=to[i];
if(v!=ff)
Max[0][v]=val[i],dfs(v,x);
}
}
int query(int x,int y) {
int ma=0,i,j;
if(dep[x]!=dep[y]) {
if(dep[y]<dep[x]) swap(x,y);
for(i=17;i>=0;--i) {
if(dep[fa[i][y]]>=dep[x]) {
ma=max(ma,Max[i][y]);
y=fa[i][y];
}
}
}
if(x==y) return ma;
for(i=17;i>=0;--i) {
if(fa[i][y]!=fa[i][x]) {
ma=max(ma,max(Max[i][y],Max[i][x]));
x=fa[i][x],y=fa[i][y];
}
}
return max(ma,max(Max[0][y],Max[0][x]));
}
int main() {
// IO::setIO("input");
int i,j,idx=0;
scanf("%d%d%d%d",&n,&m,&P,&Q);
for(i=1;i<=n;++i) {
scanf("%s",str+1);
for(j=1;j<=m;++j) {
id[i][j]=++idx;
wall[i][j]=(str[j]=='#');
}
}
for(i=1;i<=P;++i) {
int x,y;
scanf("%d%d",&x,&y);
bel[x][y]=i;
q.push(node(x,y));
}
while(!q.empty()) {
node e=q.front(); q.pop();
int x=e.x,y=e.y;
for(i=0;i<4;++i) {
int X=x+dx[i],Y=y+dy[i];
if(id[X][Y]&&!wall[X][Y]) {
if(!bel[X][Y]) {
bel[X][Y]=bel[x][y];
dis[X][Y]=dis[x][y]+1;
q.push(node(X,Y));
}
else if(bel[X][Y]!=bel[x][y]){
G[dis[X][Y]+dis[x][y]].push_back(edge(bel[X][Y],bel[x][y]));
}
}
}
}
init();
for(i=0;i<N*N;++i) {
for(j=0;j<G[i].size();++j) {
int u=G[i][j].x,v=G[i][j].y;
if(merge(u,v)) {
add(u,v,i);
add(v,u,i);
}
}
}
for(i=1;i<=P;++i) {
if(!vis[i]) {
dfs(i,0);
}
}
for(i=1;i<=Q;++i) {
int x,y;
scanf("%d%d",&x,&y);
if(find(x)!=find(y))
printf("-1
");
else
printf("%d
",query(x,y));
}
return 0;
}