将二维的点赋予一个编号,转化为一维的问题,然后二维建边后进行最小生成树即可。
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define re register
#define pir pair<int,int>
const int inf=1e9;
const int mod=998244353;
const int N=505;
using namespace std;
int n;
int mp[N][N];
struct ss{
int u,v,w;
}a[N*N*4];
int get(int x,int y){
return (x-1)*n+y;
}
bool cmp(ss g,ss h){
return g.w<h.w;
}
int fa[N*N*4];
int siz[N*N*4];
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n*n;i++){
fa[i]=i;
siz[i]=1;
}
int cnt=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i>1){
a[cnt]={get(i,j),get(i-1,j),abs(mp[i][j]-mp[i-1][j])};
cnt++;
}
if(j>1){
a[cnt]={get(i,j),get(i,j-1),abs(mp[i][j]-mp[i][j-1])};
cnt++;
}
if(i<n){
a[cnt]={get(i,j),get(i+1,j),abs(mp[i][j]-mp[i+1][j])};
cnt++;
}
if(j<n){
a[cnt]={get(i,j),get(i,j+1),abs(mp[i][j]-mp[i][j+1])};
cnt++;
}
}
}
cnt--;
sort(a+1,a+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
int x=a[i].u,y=a[i].v;
int w=a[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;
return 0;
}
}
}
return 0;
}
标签:cnt,const,get,int,问题,二维,mp,一维
From: https://www.cnblogs.com/sadlin/p/18523916