// 最小生成树 Kruskal算法 O(MlogM)
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=250010,M=N*4;
int n,m,tot,ans,mi,a[505][505],fa[N],siz[N];
pair<int,pair<int,int> >e[M]; //边集

int find(int u){ //并查集的找根
  return fa[u]==u?u:fa[u]=find(fa[u]);
}
void kruskal(){
  sort(e+1,e+m+1); //排序
  for(int i=1; i<=n; i++) fa[i]=i,siz[i]=1;
  for(int i=1; i<=m; i++){
    int x=find(e[i].second.first),y=find(e[i].second.second);
    if(x!=y){
      fa[x]=y;
      siz[y]+=siz[x];
      ans=e[i].first;
      if(siz[y]>=(n+1)/2) break;
    }
  }
  cout<<ans;
}
int P(int i,int j){ //给格点编号
  return (i-1)*n+j;
}
signed main(){
  cin>>n;
  for(int i=1;i<=n;i++)for(int j=1;j<=n;++j)cin>>a[i][j];
  for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
    if(i>1) e[++m]={abs(a[i][j]-a[i-1][j]),{P(i,j),P(i-1,j)}};
    if(j>1) e[++m]={abs(a[i][j]-a[i][j-1]),{P(i,j),P(i,j-1)}};
    if(i<n) e[++m]={abs(a[i][j]-a[i+1][j]),{P(i,j),P(i+1,j)}};
    if(j<n) e[++m]={abs(a[i][j]-a[i][j+1]),{P(i,j),P(i,j+1)}};
  }
  n*=n;
  kruskal();
}

我居然在紫堡杯模拟赛做过？？？

还有这题是生成树？？？我怎么不知道？？？

我记得当时打了个 bfs + 二分就过了啊。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define nx x+dx[i]
#define ny y+dy[i]
const int N=510;
int a[N][N],v[N][N],n,k;
int bfs(int stx,int sty)
{
	deque<PII>q;q.push_back({stx,sty});v[stx][sty]=1;int ans=1;
	while(!q.empty())
	{
		int x=q.front().fi,y=q.front().se;q.pop_front();
		for(int i=0;i<4;i++)if(nx>0&&nx<=n&&ny>0&&ny<=n&&!v[nx][ny]&&abs(a[x][y]-a[nx][ny])<=k)
			v[nx][ny]=1,q.push_back({nx,ny}),ans++;
	}
	return ans;
}
bool check(int x)
{
	k=x;memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!v[i][j])
	{
		int sum=bfs(i,j);
		if(sum>=(n*n+1)/2)return 1;
	}
	return 0;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	int l=0,r=1e6,ans=1e6;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}