[bzoj4242]水壶

最小生成树 网格图 克鲁斯卡尔重构树

题面

给出一个$n×m$的网格图，相邻点距离为$1$。图上有$p$个建筑。每次在从一个建筑到另一个建筑的所有路径中，找出使经过的相邻建筑物间最大距离最小的路径，只用输出这个最大距离。

• $n,m\leq2000,p\leq2*10^5,Q\leq2*10^5$

解析

题面没看懂去$dark\_bzoj$。。。

最大+最小，容易想到二分（货车运输），但更应该想到$Kruskal$重构树。
所以我们只要构建出这棵树，就可以$O(Qlogp)$地跳$LCA$处理询问了。

然后想想怎么构建$10^6$级别的最小生成树。
可以先把每个建筑加入队列，跑$BFS$。如果在拓展一个建筑的“势力范围”时发现这个点已经被“占领”了，这个点肯定在连接两个建筑的最短路径上。于是在这里给这两个建筑建边即可。

然后边数是$4*2000*2000=10^7$级别的，直接$sort$好像有点。。。
对每种边权的边开个$vector$来存就好了（省掉排序过程）。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
#define re register
#define il inline
#define mk make_pair
#define pb push_back
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e3+100,M=4e5+100;
int n,m,p,q,sx[N*N],sy[N*N],mx[4]={1,-1,0,0},my[4]={0,0,1,-1},dis[N][N],bl[N][N],f[M],fa[23][M],tot,h[M],cnt,w[M],d[M];
char mp[N][N];
struct Edge{int to,nxt;}e[M<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
struct node{int x,y;};
queue<node>Q;
vector<node>b[N*N];
il void BFS()
{
  fp(i,1,p) Q.push((node){sx[i],sy[i]}),bl[sx[i]][sy[i]]=i;
  while(!Q.empty())
    {
      re node u=Q.front();Q.pop();
      fp(i,0,3)
    {
      re node v=(node){u.x+mx[i],u.y+my[i]};
      if(mp[v.x][v.y]=='#') continue;
      if(!bl[v.x][v.y])
        {
          bl[v.x][v.y]=bl[u.x][u.y];
          dis[v.x][v.y]=dis[u.x][u.y]+1;
          Q.push(v);
        }
      else b[dis[v.x][v.y]+dis[u.x][u.y]].pb((node){bl[v.x][v.y],bl[u.x][u.y]});
    }
    }
}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
il void Kruskal()
{
  fp(i,1,p) f[i]=i;
  fp(i,0,n*m)
    for(re int j=0;j<b[i].size();++j)
      {
    re int u=find(b[i][j].x),v=find(b[i][j].y);
    if(u==v) continue;
    ++tot;
    f[tot]=f[u]=f[v]=tot;w[tot]=i;
    add(fa[0][u]=tot,u);add(fa[0][v]=tot,v);
      }
  fp(i,1,22)
    fp(j,1,tot)
    fa[i][j]=fa[i-1][fa[i-1][j]];
}
il void dfs(re int u)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      d[v]=d[u]+1;
      dfs(v);
    }
}
il int LCA(re int u,re int v)
{
  if(d[u]<d[v]) swap(u,v);
  fq(i,22,0) if(d[fa[i][u]]>=d[v]) u=fa[i][u];
  if(u==v) return u;
  fq(i,22,0)
    if(fa[i][u]^fa[i][v]) u=fa[i][u],v=fa[i][v];
  return fa[0][u];
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();p=gi();q=gi();tot=p;
  memset(mp,'#',sizeof(mp));
  fp(i,1,n) scanf("%s",mp[i]+1),mp[i][m+1]='#';
  fp(i,1,p) sx[i]=gi(),sy[i]=gi();
  BFS();
  Kruskal();
  fq(i,tot,1) if(!d[i]) d[i]=1,dfs(i);
  while(q--)
    {
      re int u=gi(),v=gi();
      if(find(u)^find(v)) puts("-1");
      else printf("%d\n",w[LCA(u,v)]);
    }
  return 0;
}