給你一張地圖，給你q次詢問，每次問你從A點到B點，最大能移動多大的箱子。

把每個點所能容納的最大箱子求出來（BFS，八連通，一開始將所有邊界點和障礙點入隊）。然后從大到小排序。然后用并查集將相鄰（四聯通）的點依次鏈接起來，如果不路徑壓縮的話，那么兩個節點的LCA的所能容納的箱子大小就是答案。于是用并查集輔助建樹，之后離線詢問，然后Tarjan跑個LCA即可。

O(n^2+qlog(n))，log是因為map記錄答案。

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<vector> #include<map> using namespace std; vector<int>ask[1010*1010]; int dx[]={0,1,0,-1,1,1,-1,-1},dy[]={1,0,-1,0,1,-1,1,-1}; int e,v[1010*1010],first[1010*1010],next[1010*1010]; void AddEdge(int U,int V){v[++e]=V;next[e]=first[U];first[U]=e; } struct Point{int x,y;Point(const int &x,const int &y){this->x=x;this->y=y;}Point(){} }; bool operator < (const Point &a,const Point &b){return a.x!=b.x ? a.x<b.x : a.y<b.y; } map<Point,int>anss; struct Node{Point p;int d;Node(const Point &p,const int &d){this->p=p;this->d=d;} }; int n,siz[1010][1010],Siz[1010*1010],m,K; int id[1010][1010]; bool cmp(const Point &a,const Point &b){return siz[a.x][a.y]>siz[b.x][b.y]; } char a[1010][1010]; queue<Node>q; bool vis[1010][1010]; Point ps[1010*1010]; int fa[1010*1010]; int find(int x){return x==fa[x] ? x : fa[x]=find(fa[x]); } Point qa[300010],qb[300010]; bool not_rt[1010*1010]; int ans[1010*1010]; bool VIS[1010*1010]; void LCA(int u) {ans[u]=u;for(int i=first[u];i;i=next[i]){LCA(v[i]);int f1=find(u),f2=find(v[i]);fa[f1]=f2;ans[find(u)]=u;}VIS[u]=true;for(int i=0;i<ask[u].size();i++)if(VIS[ask[u][i]]){ // printf("%d %d %d %d\n",min(u,ask[u][i]),max(u,ask[u][i]),ans[find(ask[u][i])],Siz[ans[find(ask[u][i])]]);anss[Point(min(u,ask[u][i]),max(u,ask[u][i]))]=Siz[ans[find(ask[u][i])]];} } bool sb_q[300010]; int main(){ // freopen("h.in","r",stdin);scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%s",a[i]+1);}for(int i=0;i<=n+1;++i){q.push(Node(Point(i,0),0));vis[i][0]=1;q.push(Node(Point(i,n+1),0));vis[i][n+1]=1;}for(int i=0;i<=n+1;++i){q.push(Node(Point(0,i),0));vis[0][i]=1;q.push(Node(Point(n+1,i),0));vis[n+1][i]=1;}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(a[i][j]=='#'){q.push(Node(Point(i,j),0));vis[i][j]=1;}}}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){id[i][j]=++m;}}m=0;while(!q.empty()){Node U=q.front(); q.pop();int x=U.p.x,y=U.p.y;for(int i=0;i<8;++i){int tx=x+dx[i],ty=y+dy[i];if(tx>=1 && tx<=n && ty>=1 && ty<=n && !vis[tx][ty]){q.push(Node(Point(tx,ty),U.d+1));siz[tx][ty]=Siz[id[tx][ty]]=2*U.d+1;vis[tx][ty]=1;}}} // for(int i=1;i<=n;++i){ // for(int j=1;j<=n;++j){ // printf("%d ",siz[i][j]); // } // puts(""); // }for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(siz[i][j]){ps[++m]=Point(i,j);}}}for(int i=1;i<=m;++i){fa[id[ps[i].x][ps[i].y]]=id[ps[i].x][ps[i].y];}sort(ps+1,ps+m+1,cmp);memset(vis,0,sizeof(vis));for(int i=1;i<=m;++i){int x=ps[i].x,y=ps[i].y;for(int j=0;j<4;++j){int tx=x+dx[j],ty=y+dy[j];if(a[tx][ty]=='.' && vis[tx][ty]){int rt=find(id[tx][ty]);if(rt!=find(id[x][y])){AddEdge(id[x][y],rt); // printf("%d %d\n",id[x][y],rt);not_rt[rt]=1;fa[rt]=id[x][y];}}}vis[x][y]=1;}scanf("%d",&K);for(int i=1;i<=K;++i){scanf("%d%d%d%d",&qa[i].x,&qa[i].y,&qb[i].x,&qb[i].y);int f1=find(id[qa[i].x][qa[i].y]),f2=find(id[qb[i].x][qb[i].y]);if(f1==f2){ask[id[qa[i].x][qa[i].y]].push_back(id[qb[i].x][qb[i].y]);ask[id[qb[i].x][qb[i].y]].push_back(id[qa[i].x][qa[i].y]);}else{sb_q[i]=1;}}for(int i=1;i<=m;++i){fa[id[ps[i].x][ps[i].y]]=id[ps[i].x][ps[i].y];}for(int i=1;i<=m;++i){if(!not_rt[id[ps[i].x][ps[i].y]]){LCA(id[ps[i].x][ps[i].y]);}}for(int i=1;i<=K;++i){if(sb_q[i]){puts("0");}else{printf("%d\n",anss[Point(min(id[qa[i].x][qa[i].y],id[qb[i].x][qb[i].y]),max(id[qa[i].x][qa[i].y],id[qb[i].x][qb[i].y]))]);}}return 0; }

轉載于:https://www.cnblogs.com/autsky-jadek/p/7214356.html

總結

以上是生活随笔為你收集整理的【BFS】【并查集】【Tarjan】【LCA】Gym - 101173H - Hangar Hurdles的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。