【洛谷P4955 】[USACO14JAN]越野滑雪越野滑雪

题目链接：ヾ(≧∇≦*)ゝ

对于每一个点可以向它右边的点和下面的点连边，权值就为两个点的高度差

然后再把所有的边按边权从小到大排序，并查集加点

最后判断当前集合是否涵盖所有的航点，如果是，就输出最后一条边的边权，否则就继续加点

Code:

#include<bits/stdc++.h>

#define N 500001

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

int n,m,t,cnt,tt;ll ans;

int fa[N],ct[501][501];

int mp[501][501],sz[N],u[N];

struct dqy{ll v;int x,y;}w[N];

inline bool cmp(dqy a,dqy b){return a.v<b.v;}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

inline pii getpos(int num){

	int x=num/m+(num%m!=0);

	int y=num-(x-1)*m;

	return make_pair(x,y);

}

int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

	return x*f;

}

signed main(){

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			mp[i][j]=read();

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			ct[i][j]=read(),tt+=ct[i][j];

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++){

			if(j!=m){

				w[++cnt].x=(i-1)*m+j;

				w[cnt].y=w[cnt].x+1;

				w[cnt].v=abs(mp[i][j]-mp[i][j+1]);

			}

			if(i!=n){

				w[++cnt].x=(i-1)*m+j;

				w[cnt].y=w[cnt].x+m;

				w[cnt].v=abs(mp[i][j]-mp[i+1][j]);

			}

		}

	sort(w+1,w+cnt+1,cmp);

	for(int i=1;i<=n*m;i++) fa[i]=i;

	for(int i=1;i<=n*m;i++){

		sz[i]=1;pii now=getpos(i);

		u[i]=ct[now.first][now.second];

	}

	for(int i=1;i<=cnt;i++){

		int x=w[i].x,y=w[i].y;

		int f1=find(x),f2=find(y);

		if(f1==f2) continue;

		sz[f1]+=sz[f2];

		u[f1]+=u[f2];fa[f2]=f1;

		if(u[f1]==tt){

			ans=w[i].v;

			break;

		}

	}

	printf("%lld\n",ans);

	return 0;

}