Gym - 101173H Hangar Hurdles (kruskal重构树/最小生成树+LCA)

题目大意：给出一个n*n的矩阵，有一些点是障碍，给出Q组询问，每组询问求两点间能通过的最大正方形宽度。

首先需要求出以每个点(i,j)为中心的最大正方形宽度mxl[i][j]，可以用二维前缀和+二分或者BFS求。

然后每相邻的两个点建一条权值为min(mxl[i][j],mxl[i'][j'])的边，求出整个图的最小生成树(注意边权要从大到小排序，实际上求出的是边权的“最大生成树”)或者kruskal重构树，对于每组询问(x1,y1),(x2,y2)，答案为最小生成树上两点间路径的最小边权，或者kruskal重构树上两点LCA的权值。

如果建的是最小生成树，需要启发式合并(或者路径压缩，新开一个fa数组记录合并后的)，如果建的是kruskal重构树，则需要弄个树剖或者倍增，加速求LCA的过程。

版本一(kruskal重构树+二维前缀和)：

 #include <bits/stdc++.h>

 using namespace std;

 const int N = +;

 char s[N][N];

 int n,a[N][N],mxl[N][N],m,Fa[N*N*],Tot,Q,hd[N*N*],ne,C[N*N*];

 int fa[N*N*],son[N*N*],siz[N*N*],dep[N*N*],top[N*N*];

 struct E {int v,nxt;} e[N*N*];

 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}

 void dfs1(int u,int f,int d) {

     fa[u]=f,son[u]=,siz[u]=,dep[u]=d;

     for(int i=hd[u]; ~i; i=e[i].nxt) {

         int v=e[i].v;

         if(v==fa[u])continue;

         dfs1(v,u,d+),siz[u]+=siz[v];

         if(siz[v]>siz[son[u]])son[u]=v;

     }

 }

 void dfs2(int u,int tp) {

     top[u]=tp;

     if(son[u])dfs2(son[u],top[u]);

     for(int i=hd[u]; ~i; i=e[i].nxt) {

         int v=e[i].v;

         if(v==fa[u]||v==son[u])continue;

         dfs2(v,v);

     }

 }

 int lca(int u,int v) {

     for(; top[u]!=top[v]; u=fa[top[u]])

         if(dep[top[u]]<dep[top[v]])swap(u,v);

     if(dep[u]<dep[v])swap(u,v);

     return v;

 }

 int sum(int x1,int y1,int x2,int y2) {return a[x2][y2]-a[x1-][y2]-a[x2][y1-]+a[x1-][y1-];}

 int ok(int i,int j,int x) {return !sum(i-x,j-x,i+x,j+x);}

 int bi(int i,int j,int l,int r) {

     int ret;

     while(l<=r) {

         int mid=(l+r)>>;

         if(ok(i,j,mid))l=mid+,ret=mid;

         else r=mid-;

     }

     return ret;

 }

 struct E2 {

     int x1,y1,x2,y2,c;

     bool operator<(const E2& b)const {return c>b.c;}

 } e2[N*N*];

 int fd(int x) {return Fa[x]?Fa[x]=fd(Fa[x]):x;}

 int id(int x,int y) {return (x-)*n+(y-)+;}

 void kruskal() {

     sort(e2,e2+m);

     Tot=n*n;

     memset(hd,-,sizeof hd),ne=;

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j)C[id(i,j)]=mxl[i][j];

     for(int i=; i<m; ++i) {

         int x1=e2[i].x1,y1=e2[i].y1,x2=e2[i].x2,y2=e2[i].y2,c=e2[i].c;

         int fx=fd(id(x1,y1)),fy=fd(id(x2,y2));

         if(fx==fy)continue;

         int w=++Tot;

         C[w]=c;

         Fa[fx]=Fa[fy]=w;

         addedge(w,fx),addedge(w,fy);

     }

 }

 int main() {

     scanf("%d",&n);

     for(int i=; i<=n; ++i)scanf("%s",s[i]+);

     for(int i=; i<=n; ++i)for(int j=; j<=n; ++j)a[i][j]=s[i][j]=='#';

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j)

             a[i][j]=a[i][j]+a[i-][j]+a[i][j-]-a[i-][j-];

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j)

             mxl[i][j]=s[i][j]=='#'?:bi(i,j,,min(min(i-,n-i),min(j-,n-j)))*+;

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j) {

             if(i<n)e2[m++]= {i,j,i+,j,min(mxl[i][j],mxl[i+][j])};

             if(j<n)e2[m++]= {i,j,i,j+,min(mxl[i][j],mxl[i][j+])};

         }

     kruskal();

     dfs1(Tot,,),dfs2(Tot,Tot);

     scanf("%d",&Q);

     while(Q--) {

         int x1,y1,x2,y2;

         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

         printf("%d\n",C[lca(id(x1,y1),id(x2,y2))]);

     }

 }

版本二(最小生成树+BFS)：

 #include <bits/stdc++.h>

 using namespace std;

 const int N = +;

 char s[N][N];

 int n,a[N][N],mxl[N][N],m,fa[N*N],Q,C[N*N],mxd[N*N],dep[N*N];

 struct E {

     int x1,y1,x2,y2,c;

     bool operator<(const E& b)const {return c>b.c;}

 } e[N*N*];

 struct D {int x,y;};

 queue<D> q;

 void upd(int x,int y,int c) {if(!~mxl[x][y])mxl[x][y]=c,q.push({x,y});}

 void bfs() {

     while(q.size())q.pop();

     memset(mxl,-,sizeof mxl);

     for(int i=; i<=n+; ++i)

         for(int j=; j<=n+; ++j)if(i<||i>n||j<||j>n||s[i][j]=='#')upd(i,j,);

     while(q.size()) {

         int x=q.front().x,y=q.front().y;

         q.pop();

         for(int x2=x-; x2<=x+; ++x2)

             for(int y2=y-; y2<=y+; ++y2) {

                 if(x2<||x2>n||y2<||y2>n||~mxl[x2][y2])continue;

                 upd(x2,y2,mxl[x][y]+);

             }

     }

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j)if(s[i][j]=='.')mxl[i][j]=mxl[i][j]*-;

 }

 int fd(int x) {return fa[x]?fd(fa[x]):x;}

 int id(int x,int y) {return (x-)*n+(y-)+;}

 int dfs(int u) {if(!fa[u])return ; if(dep[u])return dep[u]; return dep[u]=dfs(fa[u])+;}

 void kruskal() {

     sort(e,e+m);

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j)mxd[id(i,j)]=;

     for(int i=; i<m; ++i) {

         int x1=e[i].x1,y1=e[i].y1,x2=e[i].x2,y2=e[i].y2,c=e[i].c;

         int fx=fd(id(x1,y1)),fy=fd(id(x2,y2));

         if(fx==fy)continue;

         if(mxd[fx]>mxd[fy])swap(fx,fy);

         fa[fx]=fy,C[fx]=c,mxd[fy]=max(mxd[fy],mxd[fx]+);

     }

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j)dfs(id(i,j));

 }

 int qry(int x1,int y1,int x2,int y2) {

     int ret=min(mxl[x1][y1],mxl[x2][y2]);

     int u=id(x1,y1),v=id(x2,y2);

     while(u!=v) {

         if(dep[u]<dep[v])swap(u,v);

         ret=min(ret,C[u]);

         u=fa[u];

     }

     return ret;

 }

 int main() {

     scanf("%d",&n);

     for(int i=; i<=n; ++i)scanf("%s",s[i]+);

     bfs();

     for(int i=; i<=n; ++i)

         for(int j=; j<=n; ++j) {

             if(i<n)e[m++]= {i,j,i+,j,min(mxl[i][j],mxl[i+][j])};

             if(j<n)e[m++]= {i,j,i,j+,min(mxl[i][j],mxl[i][j+])};

         }

     kruskal();

     scanf("%d",&Q);

     while(Q--) {

         int x1,y1,x2,y2;

         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

         printf("%d\n",qry(x1,y1,x2,y2));

     }

 }