BFS+最小生成树+倍增+LCA【bzoj】4242 水壶

【bzoj4242 水壶】

Description

JOI君所居住的IOI市以一年四季都十分炎热著称。

IOI市是一个被分成纵H*横W块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有P个，编号为1...P。

JOI君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。

JOI君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要1单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此IOI市的市民一般都携带水壶出行。大小为x的水壶最多可以装x单位的水，建筑物里有自来水可以将水壶装满。

由于携带大水壶是一件很困难的事情，因此JOI君决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。

现在给出IOI市的地图和Q个询问，第i个询问(1<=i<=Q)为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”，请你对于每个询问输出对应的答案。

Input

第一行四个空格分隔的整数H,W,P,Q，表示IOI市被分成了纵H*横W块区域，有P个建筑物，Q次询问。

接下来H行，第i行(1<=i<=H)有一个长度为W的字符串，每个字符都是’.’或’#’之一，’.’表示这个位置是建筑物或原野，’#’表示这个位置是墙壁。

接下来P行描述IOI市每个建筑物的位置，第i行(1<=i<=P)有两个空格分隔的整数Ai和Bi，表示第i个建筑物的位置在第Ai行第Bi列。保证这个位置在地图中是’.’

接下来Q行，第i行(1<=i<=Q)有两个空格分隔的整数Si和Ti，表示第i个询问为“在建筑物Si和Ti之间移动，最小需要多大的水壶？”

Output

输出Q行，第i行(1<=i<=Q)一个整数，表示在建筑物Si和Ti之间移动最小需要多大的水壶。

如果无法到达，输出-1。此外，如果不需要经过原野就能到达，输出0。

好题。不过我太菜了做了好几个小时。

题目大意就是给你一个2000*2000的图形，在这个图形里有一些障碍，还有200000个点。

每次给你一对点，让你求这对点之间的点与点的路径中最小的最大值。

首先找两个点之间路径上边的最小的最大值，那么直接想到货车运输这道题，但是我们有的不是一颗树而是一个图。所以需要我们建边。

个人认为这个题最大的难点就在建边。

因为点数是200000级别的，先不管建完图跑什么算法，光是建边就建不了。

那么我们想一下，题目中给了一个很奇怪的图，所以我们从这个图入手。

很容易想到，不可能建出\(n^2\)条边，我们只能找一些点满足这两个点没有其他的点，再把这两个点连起来。所以现在来思博一下：我们把在这个图上的每个点看成一个小岛，并且每个小岛还能不断扩大，那么当小岛扩大到相邻时，我们就可以把这两个小岛代表的点连起来，这样的连边策略一定是最优的。

以为首先，我们保证了每个点之间都可以互相到达，其次我们要求的是最大边最小，所以尽可能的让边短一点，那就肯定是找最近的，小岛策略正好符合。

所以我们建边的方式就是BFS，将每一个点扔到队列里，再以每个点为中心向四个方向扩散，如果扩散到的点没有被标记，那么就打上标记化作这个点的领地。相反，如果扩散到的点被标记，那么我们认为这两个小岛相连了，那么就直接连一条边就行。

有考虑到会有障碍，所以在BFS的时候记一个步数就行。

建完边之后问题就变得可做了很多。

我们先跑一遍MST，然后直接倍增LCA就可以了。

细节比较多，好题。

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

const int wx=2017;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}

	return sum*f;

}

int num,tot;

int n,m,qq,p;

char c[200017];

queue<int > q;

int dx[]={0,1,0,-1,0};

int dy[]={0,0,1,0,-1};

int a[wx][wx],vis[wx][wx],dis[wx][wx];

int d[200017][21],f[200017][21],fa[200017];

int dep[4000017];

int head[4000017r];

struct node{

	int l,r,d;

	friend bool operator < (const node& a,const node& b){

		return a.d<b.d;

	}

}t[4000017];

struct e{

	int nxt,to,dis;

}edge[4000017];

void add(int from,int to,int dis){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	edge[num].dis=dis;

	head[from]=num;

}

int find(int x){

	if(fa[x]==x)return x;

	return fa[x]=find(fa[x]);

}

void bfs(){

	while(q.size()){

		int ux=q.front();q.pop();

		int uy=q.front();q.pop();

		for(int i=1;i<=4;i++){

			int ex=ux+dx[i];

			int ey=uy+dy[i];

			if(ex<1||ex>n||ey<1||ey>m||a[ex][ey])continue;

			if(dis[ex][ey]==-1){

				vis[ex][ey]=vis[ux][uy];dis[ex][ey]=dis[ux][uy]+1;

				q.push(ex);q.push(ey);

			}

			else {

				if(vis[ex][ey]!=vis[ux][uy]){

					t[++tot].l=vis[ux][uy];

					t[tot].r=vis[ex][ey];

					t[tot].d=dis[ex][ey]+dis[ux][uy];

				}

			}

		}

	}

}

void Kruskal(){

	for(int i=1;i<=p;i++)fa[i]=i;

	sort(t+1,t+1+tot);

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

		int x=find(t[i].l);int y=find(t[i].r);

		if(x==y)continue;

		add(x,y,t[i].d);

		add(y,x,t[i].d);

		fa[x]=y;

	}

}

void dfs(int u,int ff,int gg){

	dep[u]=dep[ff]+1;f[u][0]=ff;d[u][0]=gg;

	for(int i=1;i<=20;i++){

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

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

	}

	for(int i=head[u];i!=-1;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==ff)continue;

		dfs(v,u,edge[i].dis);

	}

}

int FFF(int x,int y){

	int maxn=0;

	if(dep[x]<dep[y])swap(x,y);

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

		if(dep[f[x][i]]>=dep[y]){

			maxn=max(maxn,d[x][i]);

			x=f[x][i];

		}

	}

	if(x==y)return maxn;

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

		if(f[x][i]!=f[y][i]){

			maxn=max(maxn,d[x][i]);

			maxn=max(maxn,d[y][i]);

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

		}

	}

	return max(maxn,max(d[x][0],d[y][0]));

}

int main(){

	n=read();m=read();p=read();qq=read();

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

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

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

			a[i][j]=(c[j]=='#');

		}

	}

	memset(head,-1,sizeof head);

	memset(dis,-1,sizeof dis);

//	memset(d,-1,sizeof d);

	for(int i=1;i<=p;i++){

		int x,y;

		x=read();y=read();

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

		q.push(x);q.push(y);

	}

	bfs();

	Kruskal();

	for(int i=1;i<=p;i++){

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

	}

	for(int i=1;i<=qq;i++){

		int x,y;

		x=read();y=read();

		if(find(x)!=find(y))printf("-1\n");

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

	}

	return 0;

}

巴特西

BFS+最小生成树+倍增+LCA【bzoj】4242 水壶

【bzoj4242 水壶】

Description

Input

Output

最新文章

热门文章