Tractor S--二维转一维，然后最小生成树

P3073 [USACO13FEB] Tractor S - 洛谷

转成一维点图，然后最小生成树，最后的最大值就是最后一个点，记得记录维护连通块

同样的二维转一维---Cow Ski Area G---二维图转一维+tarjan缩点-CSDN博客

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
int n,m;
int a[505][505];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct no
{int u,v;int w;
}; 
struct cmp
{bool operator()(no &a,no &b)const{return a.w>b.w;}
};
priority_queue<no,vector<no> ,cmp> pq;
int fa[250004];
bool bo[250004];
int find(int x)
{if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
void dfs(int x,int y)
{int p1=(x-1)*n+y;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=n){int p2=(tx-1)*n+ty;pq.push({p1,p2,abs(a[x][y]-a[tx][ty])});}}
}set<int> an;
ll s;
int k[250004];
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);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++) {dfs(i,j);	}} for(int i=1;i<=n*n;i++) fa[i]=i,k[i]=1;while(pq.size()){no t=pq.top();pq.pop();if(find(t.u)!=find(t.v)){k[find(t.v)]+=k[find(t.u)];fa[find(t.u)]=find(t.v);if(k[find(t.v)]>=(n*n/2)){cout<<t.w;return 0;}}}return 0;
}