[关闭]
@ysner 2018-09-26T14:48:16.000000Z 字数 2437 阅读 1627

[bzoj4242]水壶

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


题面

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

解析

题面没看懂去。。。

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

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

然后边数是级别的,直接好像有点。。。
对每种边权的边开个来存就好了(省掉排序过程)。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #include<vector>
  9. #define ll long long
  10. #define re register
  11. #define il inline
  12. #define mk make_pair
  13. #define pb push_back
  14. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  15. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  16. using namespace std;
  17. const int N=2e3+100,M=4e5+100;
  18. 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];
  19. char mp[N][N];
  20. struct Edge{int to,nxt;}e[M<<1];
  21. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  22. il ll gi()
  23. {
  24. re ll x=0,t=1;
  25. re char ch=getchar();
  26. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  27. if(ch=='-') t=-1,ch=getchar();
  28. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  29. return x*t;
  30. }
  31. struct node{int x,y;};
  32. queue<node>Q;
  33. vector<node>b[N*N];
  34. il void BFS()
  35. {
  36. fp(i,1,p) Q.push((node){sx[i],sy[i]}),bl[sx[i]][sy[i]]=i;
  37. while(!Q.empty())
  38. {
  39. re node u=Q.front();Q.pop();
  40. fp(i,0,3)
  41. {
  42. re node v=(node){u.x+mx[i],u.y+my[i]};
  43. if(mp[v.x][v.y]=='#') continue;
  44. if(!bl[v.x][v.y])
  45. {
  46. bl[v.x][v.y]=bl[u.x][u.y];
  47. dis[v.x][v.y]=dis[u.x][u.y]+1;
  48. Q.push(v);
  49. }
  50. else b[dis[v.x][v.y]+dis[u.x][u.y]].pb((node){bl[v.x][v.y],bl[u.x][u.y]});
  51. }
  52. }
  53. }
  54. il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
  55. il void Kruskal()
  56. {
  57. fp(i,1,p) f[i]=i;
  58. fp(i,0,n*m)
  59. for(re int j=0;j<b[i].size();++j)
  60. {
  61. re int u=find(b[i][j].x),v=find(b[i][j].y);
  62. if(u==v) continue;
  63. ++tot;
  64. f[tot]=f[u]=f[v]=tot;w[tot]=i;
  65. add(fa[0][u]=tot,u);add(fa[0][v]=tot,v);
  66. }
  67. fp(i,1,22)
  68. fp(j,1,tot)
  69. fa[i][j]=fa[i-1][fa[i-1][j]];
  70. }
  71. il void dfs(re int u)
  72. {
  73. for(re int i=h[u];i+1;i=e[i].nxt)
  74. {
  75. re int v=e[i].to;
  76. d[v]=d[u]+1;
  77. dfs(v);
  78. }
  79. }
  80. il int LCA(re int u,re int v)
  81. {
  82. if(d[u]<d[v]) swap(u,v);
  83. fq(i,22,0) if(d[fa[i][u]]>=d[v]) u=fa[i][u];
  84. if(u==v) return u;
  85. fq(i,22,0)
  86. if(fa[i][u]^fa[i][v]) u=fa[i][u],v=fa[i][v];
  87. return fa[0][u];
  88. }
  89. int main()
  90. {
  91. memset(h,-1,sizeof(h));
  92. n=gi();m=gi();p=gi();q=gi();tot=p;
  93. memset(mp,'#',sizeof(mp));
  94. fp(i,1,n) scanf("%s",mp[i]+1),mp[i][m+1]='#';
  95. fp(i,1,p) sx[i]=gi(),sy[i]=gi();
  96. BFS();
  97. Kruskal();
  98. fq(i,tot,1) if(!d[i]) d[i]=1,dfs(i);
  99. while(q--)
  100. {
  101. re int u=gi(),v=gi();
  102. if(find(u)^find(v)) puts("-1");
  103. else printf("%d\n",w[LCA(u,v)]);
  104. }
  105. return 0;
  106. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注