自动搬运

查看原文

来自洛谷，原作者为

	daihang **

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

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

以下是正文

并查集+最小生成树算法

题目要求最大值最小化，满足最小生成树的性质

Details

1. 建图。除边缘外的每个点均可以向上下左右四个方向连边，点的编号可表示为: n*(i-1)+j (i为行,j为列)

实现代码：

int ex(int i,int j){
	return (i-1)*n+j;
}

边的权值即为两点高度差的绝对值

2. 如何维护集合的大小。初始化将size全设为1，后续再进行合并操作(merge)时，将旧的集合的大小更新到新的集合上。在新的集合大小大于(n*n)/2时，输出当前边的权值即可。

实现代码：

x=find(x);//find函数是为了找父亲
y=find(y);
if(x!=y){
	fa[x]=y;
	siz[y]+=siz[x];
	if(siz[y]>=(n*n+1)/2){
		cout<<w<<endl;
		return 0;
	}
}

3. 最小生成树Kruskal 不解释

不会的可以找模板题P3366 【模板】最小生成树

最后送上代码，祝各位水题切题愉快

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n;
int mp[maxn][maxn];
inline int read(){//快读
	int x=0,y=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')y=-y; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*y;
}
int fa[maxn*maxn];
int siz[maxn*maxn];
struct node{
	int u,v,w;
	node(){}
	node(int uu,int vv,int ww){
		u=uu;
		v=vv;
		w=ww;
	}
}edge[maxn*maxn*4];
bool cmp(const node &a,const node &b){
	return a.w<b.w;
}
int ans=0;
void init(){
	for(int i=1;i<=n*n;i++){
		fa[i]=i;
		siz[i]=1;
	}
}
int find(int x){
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
int ex(int i,int j){
	return (i-1)*n+j;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=read();
		}
	}
	init();
	int tp=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(i>1){
				edge[tp]=node(ex(i,j),ex(i-1,j),abs(mp[i-1][j]-mp[i][j]));
				tp++;
			}
			if(j>1){
				edge[tp]=node(ex(i,j),ex(i,j-1),abs(mp[i][j-1]-mp[i][j]));
				tp++;
			}
			if(i<n){
				edge[tp]=node(ex(i,j),ex(i+1,j),abs(mp[i+1][j]-mp[i][j]));
				tp++;
			}
			if(j<n){
				edge[tp]=node(ex(i,j),ex(i,j+1),abs(mp[i][j+1]-mp[i][j]));
				tp++;
			}
		}
	}
	sort(edge+1,edge+tp,cmp);
	for(int i=1;i<tp;i++){
		int x=edge[i].u;
		int y=edge[i].v;
		int w=edge[i].w;
		x=find(x);
	    y=find(y);
	    if(x!=y){
		    fa[x]=y;
		    siz[y]+=siz[x];
		    if(siz[y]>=(n*n+1)/2){
			    cout<<w<<endl;
			    return 0;
		    }
	    }
	}
}

写题解不易，求个赞