Description
JOI君所居住的IOI市以一年四季都十分炎热著称。
IOI市是一个被分成纵H*横W块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有P个，编号为1...P。
JOI君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。
JOI君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要1单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此IOI市的市民一般都携带水壶出行。大小为x的水壶最多可以装x单位的水，建筑物里有自来水可以将水壶装满。
由于携带大水壶是一件很困难的事情，因此JOI君决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。
现在给出IOI市的地图和Q个询问，第i个询问(1<=i<=Q)为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”，请你对于每个询问输出对应的答案。
Input
第一行四个空格分隔的整数H,W,P,Q，表示IOI市被分成了纵H*横W块区域，有P个建筑物，Q次询问。
接下来H行，第i行(1<=i<=H)有一个长度为W的字符串，每个字符都是’.’或’#’之一，’.’表示这个位置是建筑物或原野，’#’表示这个位置是墙壁。
接下来P行描述IOI市每个建筑物的位置，第i行(1<=i<=P)有两个空格分隔的整数Ai和Bi，表示第i个建筑物的位置在第Ai行第Bi列。保证这个位置在地图中是’.’
接下来Q行，第i行(1<=i<=Q)有两个空格分隔的整数Si和Ti，表示第i个询问为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”
Output
输出Q行，第i行(1<=i<=Q)一个整数，表示在建筑物Si和Ti之间移动最小需要多大的水壶。如果无法到达，输出-1。此外，如果不需要经过原野就能到达，输出0。
Sample Input
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4
Sample Output
3
4
4
2
HINT
1<=H<=2000
1<=W<=2000
2<=P<=210^5
1<=Q<=210^5
1<=Ai<=H(1<=i<=P)
1<=Bi<=W(1<=i<=P)
(Ai,Bi)≠(Aj,Bj)(1<=i<j<=P)
1<=Si < Ti <=P(1<=i<=Q)
题目分析
思路很明确 我们先求出每两点的最小距离 然后跑路径最大权的货车运输(最小生成树+倍增)
关键是两点间最小距离怎么求 肯定不能暴力BFS
我们先把所有点都推进队列里 以每个点向外拓展 并且记录每个点被哪些建筑物拓展到的
如果一个点拓展到了一个之前被拓展的点 那么把两点所属的建筑物连边
这样做边数是HW 但我们不能将4*10^6边按边权排序 由于边权极限HW 那我们就用vector存储即可
注意用并查集判断两点是否在同一联通块内
注意图有可能是森林
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,p,lo;
char sa[2101][2101];
struct your
{
int x,y;
}sta[200100];
struct my
{
int x,y,c;
}e[4000100];
int cnt,belong[2101][2101],di[2101][2101];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
vector<your> sv[4000010];
void bfs()
{
queue<your>q;
for(int i=1;i<=p;i++) q.push(sta[i]),belong[sta[i].x][sta[i].y]=i;
while(q.size())
{
your x=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int dxx=dx[i]+x.x,dyy=dy[i]+x.y;
if(dxx<1||dxx>n||dyy<1||dyy>m||sa[dxx][dyy]=='#') continue ;
if(!di[dxx][dyy]&&!belong[dxx][dyy])
di[dxx][dyy]=di[x.x][x.y]+1,belong[dxx][dyy]=belong[x.x][x.y],q.push((your){dxx,dyy});
if(belong[dxx][dyy]!=belong[x.x][x.y])
sv[di[dxx][dyy]+di[x.x][x.y]].push_back((your){belong[dxx][dyy],belong[x.x][x.y]});
}
}
}
int f[200100];
int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
bool cmp(my j,my k) { return j.c<k.c; }
int tot,head[200100],to[400100],net[400100],val[400100];
void add(int x,int y,int c) { net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c; }
void kru()
{
int nm=0;
for(int i=0;i<=n*m;i++)
{
for(int j=0;j<sv[i].size();j++)
{
your tmp=sv[i][j];
int dx=find(tmp.x),dy=find(tmp.y);
if(dx!=dy) f[dx]=dy,nm++,add(tmp.x,tmp.y,i),add(tmp.y,tmp.x,i);
if(nm==p-1) return ;
}
}
}
int deep[200100],fa[200100][20],mi[200100][20];
void dfs(int x)
{
deep[x]=deep[fa[x][0]]+1;
for(int i=1;fa[x][i-1];i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
mi[x][i]=max(mi[x][i-1],mi[fa[x][i-1]][i-1]);
}
for(int i=head[x];i;i=net[i])
if(to[i]!=fa[x][0])
fa[to[i]][0]=x,mi[to[i]][0]=val[i],dfs(to[i]);
}
int ask(int x,int y)
{
int sum=0;
if(deep[x]<deep[y]) swap(x,y);
for(int temp=18;temp>=0;temp--)
if(deep[fa[x][temp]]>=deep[y])
sum=max(sum,mi[x][temp]),x=fa[x][temp];
if(x==y) return sum;
for(int temp=18;temp>=0;temp--)
if(fa[x][temp]!=fa[y][temp])
sum=max(sum,max(mi[x][temp],mi[y][temp])),x=fa[x][temp],y=fa[y][temp];
return max(sum,max(mi[x][0],mi[y][0]));
}
int main()
{
scanf("%d%d%d%d",&n,&m,&p,&lo);
for(int i=1;i<=n;i++) scanf("%s",sa[i]+1);
for(int i=1;i<=p;i++) scanf("%d%d",&sta[i].x,&sta[i].y),f[i]=i;
bfs(),kru();
for(int i=1;i<=p;i++) if(!deep[i]) dfs(i);
for(int x,y,i=1;i<=lo;i++)
{
scanf("%d%d",&x,&y);
if(find(x)!=find(y)) printf("-1\n");
else printf("%d\n",ask(x,y));
}
return 0;
}
