【平面图MST+树上RMQ】水壶

传送门:BZOJ4242

JOI


思路:

  • 可以发现答案为两个点在MST的路径上边权最大的边;
  • 先求出所有点的MST,直接连边肯定没希望,考虑用BFS,每个点向外扩展,相遇了才连边,其它边不可能出现在MST中;
  • 然后求出MST以后就是树上RMQ,树上路径倍增???似乎可以树剖+ST。

注意:

  • 开始建完图后边数是4NM,N,M为网格图的长宽;
  • 如果用计数排序注意边权大小;
  • 注意卡空间。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 200030
#define M 2010
const int dic[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int n,m,p,t,x,y,z,tot,tot2,clk,st[N][20],Log[N],cnt[N*10],par[N],fa[N],deep[N],size[N],dfn[N],top[N],d[N*32],head2[N],q[N*20][4],dist[M][M],vis[M][M];
char s[M][M];
struct edge2{int u,v,dist;}ee[N*32];
struct edge{int u,v,dist,nxt;}e[N*2];
void add(int x,int y,int dd){ee[++tot].v=y; ee[tot].u=x; ee[tot].dist=dd;}
void add2(int x,int y,int dd){e[++tot2].v=y; e[tot2].u=x; e[tot2].dist=dd; e[tot2].nxt=head2[x]; head2[x]=tot2;}
int getint(){
char ch; int sum=0;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
return sum;
}
void bfs(){
int tt=0,ww=0;
for (int i=1;i<=p;i++){
x=getint(); y=getint();
q[++ww][0]=x; q[ww][1]=y; q[ww][2]=i; q[ww][3]=dist[x][y]=0; vis[x][y]=i;
}
while (tt<ww){
int x=q[++tt][0],y=q[tt][1],i=q[tt][2],step=q[tt][3];
for (int j=0;j<4;j++){
int nx=x+dic[j][0],ny=y+dic[j][1];
if (nx<1 || nx>n || ny<1 || ny>m) continue;
if (!vis[nx][ny] && s[nx][ny]=='.'){
vis[nx][ny]=i;
q[++ww][0]=nx; q[ww][1]=ny; q[ww][2]=i; q[ww][3]=dist[nx][ny]=step+1;
}
else
if (s[nx][ny]=='.' && i!=vis[nx][ny]){
add(i,vis[nx][ny],step+dist[nx][ny]);
add(vis[nx][ny],i,step+dist[nx][ny]);
}
}
}
}
int gfa(int x){return x==par[x]?x:par[x]=gfa(par[x]);}
void mst(){
int mx=0; for (int i=1;i<=tot;i++){cnt[ee[i].dist]++; mx=max(mx,ee[i].dist);}
for (int i=1;i<=mx;i++) cnt[i]+=cnt[i-1];
for (int i=1;i<=tot;i++) d[cnt[ee[i].dist]--]=i;
for (int i=1;i<=p;i++) par[i]=i;
for (int i=1,j;i<=tot;i++){
j=d[i]; int u=ee[j].u,v=ee[j].v;
int U=gfa(u),V=gfa(v); if (gfa(U)!=gfa(V)){par[U]=par[V]; add2(u,v,ee[j].dist); add2(v,u,ee[j].dist);}
}
}
void dfs1(int u){
if (!fa[u]) fa[u]=u; deep[u]=deep[fa[u]]+1; size[u]=1;
for (int i=head2[u],v;i;i=e[i].nxt){
if ((v=e[i].v)!=fa[u]){fa[v]=u; dfs1(v); size[u]+=size[v];}}
}
void dfs2(int u){
if (!top[u]) top[u]=u; dfn[u]=++clk; int t=0;
for (int i=head2[u],v;i;i=e[i].nxt){
if (fa[u]==(v=e[i].v)) d[u]=e[i].dist;
if (fa[u]!=v && size[v]>size[t]) t=v;
}
if (!t) return; top[t]=top[u]; dfs2(t);
for (int i=head2[u],v;i;i=e[i].nxt)
if (fa[u]!=(v=e[i].v) && v!=t) dfs2(v);
}
int lca(int u,int v){
for (;top[u]!=top[v];u=fa[top[u]]) if (deep[top[u]]<deep[top[v]]) swap(u,v);
return deep[u]<deep[v]?u:v;
}
void build(){
for (int i=1;i<=p;i++) st[dfn[i]][0]=d[i];
for (int i=1;1<<i<=p;i++)
for (int j=1;j+(1<<i)-1<=p;j++) st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int query(int u,int v){
int ret=0;
if (deep[top[u]]>deep[v]){
int ll=Log[dfn[u]-dfn[top[u]]+1];
ret=max(st[dfn[top[u]]][ll],st[dfn[u]-(1<<ll)+1][ll]);
return max(ret,query(fa[top[u]],v));
}
int l=dfn[top[u]],r=dfn[u],mid,tmp=-1;
while (l<=r){mid=(l+r)>>1; if (mid<=dfn[v]) l=mid+1; else{tmp=mid; r=mid-1;}}
if (tmp!=-1){int ll=Log[dfn[u]-tmp+1]; return max(st[tmp][ll],st[dfn[u]-(1<<ll)+1][ll]);}
return 0;
}
int main(){
n=getint(); m=getint(); p=getint(); t=getint();
for (int i=1,j=0;i<=p;i++){if (1<<(j+1)<=i) j++; Log[i]=j;}
for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
bfs(); mst(); memset(d,0,sizeof d);
for (int i=1;i<=p;i++) if (!fa[i]){dfs1(i); dfs2(i);} build();
for (int i=1;i<=t;i++){
x=getint(); y=getint();
if (gfa(x)!=gfa(y)){puts("-1"); continue;} z=lca(x,y);
printf("%d\n",max(query(x,z),query(y,z)));
}
return 0;
}