【平面图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;
}