最小生成树Kruskal+LCA+bfs【bzoj4242】水壶

一道好题。货车运输的既视感.

难点在于建边,我们可以从建筑物向外扩展,这时候,如果扩展出来的地方相互接触,则可以直接对中心的建筑物之间直接建边即可.具体建边的话见我的大佬同桌王小呆的博客

建边出来跑\(Kruskal\),然后跑维护最大值的带权\(LCA\)即可。

代码

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<iostream>

#define N 2008

#define R register

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

struct cod{int x,y;};

int n,m,P,Q;

int res[N][N],dis[N][N];

int vis[N][N],fa[200008];

const int ax[]={0,0,-1,1};

const int ay[]={1,-1,0,0};

int head[4000018],tot,ttt,cnt;

struct code{int u,v,w;}edge[5000018],e[5000018];

char s[N+2];

inline void add(int x,int y,int z)

{

	e[++ttt].u=head[x];

	e[ttt].v=y;

	e[ttt].w=z;

	head[x]=ttt;

}

inline bool ccp(const code&a,const code&b)

{

	return a.w<b.w;

}

queue<cod>q;

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

inline int bfs()

{

	while(!q.empty())

	{

		int x=q.front().x,y=q.front().y;

		q.pop();

		for(R int i=0;i<4;i++)

		{

			int nx=x+ax[i],ny=y+ay[i];

			if(nx<1 or nx>n or ny>m or ny<1 or res[nx][ny])continue;

			if(dis[nx][ny]==-1)

			{

				vis[nx][ny]=vis[x][y];

				dis[nx][ny]=dis[x][y]+1;

				q.push((cod){nx,ny});

			}

			else if(vis[nx][ny]!=vis[x][y])

			{

				edge[++tot].u=vis[nx][ny];

				edge[tot].v=vis[x][y];

				edge[tot].w=dis[x][y]+dis[nx][ny];

			}

		}

	}

}

inline void kruskal()

{

	sort(edge+1,edge+tot+1,ccp);

	for(R int i=1;i<=tot;i++)

	{

		R int u=edge[i].u,v=edge[i].v,w=edge[i].w;

		R int fu=find(u),fv=find(v);

		if(fu==fv)continue;

		fa[fu]=fv;add(fu,fv,w);add(fv,fu,w);cnt++;

		if(cnt==P-1)break;

	}

}

int gw[200008][21],f[200008][21],depth[400008];

void dfs(int u,int fa,int dis)

{

	f[u][0]=fa;gw[u][0]=dis;depth[u]=depth[fa]+1;

	for(R int i=1;(1<<i)<=depth[u];i++)

	{

		f[u][i]=f[f[u][i-1]][i-1];

		gw[u][i]=max(gw[u][i-1],gw[f[u][i-1]][i-1]);

	}

	for(R int i=head[u];i;i=e[i].u)

	{

		if(e[i].v==fa)continue;

		dfs(e[i].v,u,e[i].w);

	}

}

inline int lca(int x,int y)

{

	int res=-2147483644;

	if(depth[x]>depth[y])swap(x,y);

	for(R int i=20;i>=0;i--)

		if(depth[x]+(1<<i)<=depth[y])

			res=max(res,gw[y][i]),y=f[y][i];

	if(x==y)return res;

	for(R int i=20;i>=0;i--)

	{

		if(f[x][i]==f[y][i])continue;

		res=max(res,max(gw[x][i],gw[y][i]));

		y=f[y][i],x=f[x][i];

	}

	return max(res,max(gw[x][0],gw[y][0]));

}

int main()

{

	in(n),in(m),in(P),in(Q);

	for(R int i=1;i<=n;i++)

	{

		scanf("%s",s+1);

		for(R int j=1;j<=m;j++)

		{

			res[i][j]= s[j]=='#';

			dis[i][j]=-1;

		}

	}

	for(R int i=1,x,y;i<=P;i++)

	{

		in(x),in(y);fa[i]=i;

		dis[x][y]=0;vis[x][y]=i;

		q.push((cod){x,y});

	}

	bfs();

	kruskal();

	for(R int i=1;i<=P;i++)

		if(!f[i][0])dfs(i,0,0);

	for(R int i=1,x,y;i<=Q;i++)

	{

		in(x),in(y);

		if(find(x)!=find(y))puts("-1");

		else printf("%d\n",lca(x,y));

	}

}