自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:40:07，当前版本为作者最后更新于2018-07-03 18:16:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

竟然没有并查集的代码？

题目大意

在一个$n\times m$的矩阵中，每个点都有相应的高度，规定两点间的高度差不大于$D$就当这两个点联通，先要求出最小的$D$使得给定的点都联通

解题思路

显然，假如$D=50$，满足要求的话，那么$D=51$也必定满足要求，说玄学一点就是答案具有单调性

那么我们就可以用二分来处理啦！

对于能否滑行，这里用的是并查集的判定

若两点间高度不大于$mid$（当前二分的$D$），则将它们的祖先合并，最后判断一下所有要求连接的点之间是否联通就行啦！

代码

$Very\ \ Important$ 时间复杂度:$O(logMaxhigh\times nm)$ 最高复杂度为:$O(log100000000\times 250000)\approx O(7500000)$能过

#include<cstdio>
#include<cstring>
#define id(i,j) ~-i*m+j//即每个点的编号，相当于(i-1)*m+j
using namespace std;
int h[501][501],f[250001],a[250001],len;//h是每个点的高度，f是并查集数组，a是需要保证联通的点，len是a数组长度
int ans,l,r,n,m,mid;
const short dx[4]={-1,0,1,0};
const short dy[4]={0,1,0,-1};
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void add(int x,int y){f[find(x)]=find(y);return;}
int abs(int x){return x<0?-x:x;}
bool check(int high)
{
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)f[id(i,j)]=id(i,j);//初始化
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	  for(int k=0;k<4;k++)//向周围四个点连边
	  {
	  	int nx=i+dx[k],ny=j+dy[k];
	 	if(nx<1||ny<1||nx>n||ny>m) continue;//爆出范围跳过
	 	if(abs(h[i][j]-h[nx][ny])>high)continue;//超过高度跳过
	 	add(id(i,j),id(nx,ny));//连边
      }
	for(int i=1;i<len;i++) 
	if(find(a[i])!=find(a[i+1])) return false;//判断是否能联通
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {scanf("%d",&h[i][j]);if(h[i][j]>r) r=h[i][j];}//保存最大的r
	for(int i=1;i<=n;i++) for(int j=1,t;j<=m;j++) 
	{scanf("%d",&t);if(t) a[++len]=id(i,j);}//保存
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))//判断
		{
			ans=mid;
			r=mid-1;//调整右边界
		}
		else l=mid+1;//调整左边界
	}
	printf("%d",ans);//输出
}