題目鏈接：點擊查看

題目大意：給出一個 $n?n$ 的矩陣，有些位置存在障礙物，現在有 $q$ 次詢問，每次詢問給出兩個點 $st=(x1,y1),ed=(x2,y2)$，需要回答從 $st$ 開始推箱子，可以推到 $ed$ 的最大箱子的邊長是多少

題目分析：首先不難想到預處理出以每個點為中心時，可以放置箱子的最大邊長，可以通過二維前綴和+二分的思路在 $O(n^{2}logn)$ 的復雜度內求解，不過代碼不是很好寫。考慮到本題規定了正方形的邊長一定是奇數，在紙上畫畫不難發現，當正方形確定后，如果每次可以擴展八個方向，那么正方形的四個邊界以及對角到中心的距離都是相等的，依據這個可以用 $flood?fill$ 算法在 $O(n^2)$ 的時間復雜度內實現，且代碼相對簡單，注意不要忘記考慮邊界帶來的影響。

現在問題轉換為了，需要找到一條 $st$ 到 $ed$ 的路徑，滿足路徑上的最小值最大。這不就是最小瓶頸樹的模板題嗎？因為本題是令最小值最大，所以對原圖構造一個最大生成樹即可，那么后續的每次詢問，都轉換成了：在最大生成樹上， $st$ 到 $ed$ 這條路徑上邊權的最小值是多少。

為了避免在樹上邊權轉點權的細節操作，不如直接對上述操作構建一下克魯斯卡爾重構樹，這樣一來每次詢問就變成了詢問兩點的 $LCA$ 的權值了

代碼：

// Problem: Hangar Hurdles // Contest: Virtual Judge - Gym // URL: https://vjudge.net/problem/Gym-101173H // Memory Limit: 524 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=2e6+100; const int b[8][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1}; char maze[1010][1010]; int id[1010][1010],d[1010][1010],tot; struct Ex_Kruskal {struct Edge{int x,y,w;bool operator<(const Edge& t)const{return w>t.w;}}edge[N];int f[N],val[N],dp[N][25],deep[N],index,cnt,n;vector<int>node[N];void init(int n){cnt=tot=0;index=n;for(int i=0;i<=n<<1;i++){f[i]=i;node[i].clear();}}int find(int x){return f[x]==x?x:f[x]=find(f[x]);}void addedge(int x,int y,int w){edge[++cnt]={x,y,w};}void solve(){sort(edge+1,edge+1+cnt);for(int i=1;i<=cnt;i++){int xx=find(edge[i].x),yy=find(edge[i].y);if(xx!=yy){f[xx]=f[yy]=++index;node[index].push_back(xx);node[index].push_back(yy);val[index]=edge[i].w;}}n=index;for(int i=1;i<=n;i++)if(find(i)==i)dfs(i,0,0);}void dfs(int u,int fa,int dep){deep[u]=dep;dp[u][0]=fa;for(int i=1;i<=20;i++) {dp[u][i]=dp[dp[u][i-1]][i-1];}for(auto v:node[u])dfs(v,u,dep+1);}int LCA(int a,int b){if(deep[a]<deep[b])swap(a,b);for(int i=20;i>=0;i--)if(deep[a]-deep[b]>=(1<<i))a=dp[a][i];if(a==b)return a;for(int i=20;i>=0;i--)if(dp[a][i]!=dp[b][i]){a=dp[a][i];b=dp[b][i];}return dp[a][0];}int cal(int x,int y) {return val[LCA(x,y)];} }T; void bfs(int n) {memset(d,-1,sizeof(d));queue<pair<int,int>>q;for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {if(maze[i][j]=='#') {q.push({i,j});d[i][j]=0;}}}for(int i=1;i<=n;i++) {d[0][i]=d[i][0]=d[n+1][i]=d[i][n+1]=0;q.push({0,i});q.push({i,0});q.push({n+1,i});q.push({i,n+1});}while(q.size()) {int x,y;tie(x,y)=q.front();q.pop();for(int i=0;i<8;i++) {int xx=x+b[i][0],yy=y+b[i][1];if(xx<=0||xx>n||yy<=0||yy>n) {continue;}if(d[xx][yy]!=-1) {continue;}d[xx][yy]=d[x][y]+1;q.push({xx,yy});}}for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {if(d[i][j]) {d[i][j]=d[i][j]*2-1;}}} } void build(int n) {for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {if(i+1<=n) {T.addedge(id[i][j],id[i+1][j],min(d[i][j],d[i+1][j]));}if(j+1<=n) {T.addedge(id[i][j],id[i][j+1],min(d[i][j],d[i][j+1]));}}} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++) {scanf("%s",maze[i]+1);for(int j=1;j<=n;j++) {id[i][j]=++tot;}}T.init(n*n);bfs(n);build(n);T.solve();int q;read(q);while(q--) {int x1,y1,x2,y2;read(x1),read(y1),read(x2),read(y2);printf("%d\n",T.cal(id[x1][y1],id[x2][y2]));}return 0; }

總結

以上是生活随笔為你收集整理的Gym - 101173H Hangar Hurdles(bfs+克鲁斯卡尔重构树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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