40分求助
查看原帖
40分求助
25891
沧桑の天骄楼主2021/11/8 21:50
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline ll read()
{
	ll x=0,w=1;
	char aa=getchar();
	while(aa<'0'||aa>'9'){
		if(aa=='-'){
			w=-1;
		}
		aa=getchar();
	}
	while(aa>='0'&&aa<='9'){
		x=(x<<3)+(x<<1)+aa-'0';
		aa=getchar();
	}
	return x*w;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-1;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
const int N=510;

ll n,m,t,mp[N][N],top;
ll fa[N*N],size[N*N],jl[N*N];
ll ans;
struct node{
	int x,y;
	ll z;
	node(){}
	node(int x1,int y1,ll z1){
		x=x1;
		y=y1;
		z=z1;
	}
}e[4*N*N];

void init(){
	for(int i=1;i<=n*m;i++){
		fa[i]=i;
		size[i]=1;
	}
}

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

int ex(int x,int y){
	return (x-1)*m+y;
}

bool cmp(node x,node y){
	return x.z<y.z;
}

int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),m=read(),t=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			mp[i][j]=read();
		}
	}
	init();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			jl[ex(i,j)]=read();
			if(i<n){
				e[++top]=node(ex(i,j),ex(i+1,j),abs(mp[i][j]-mp[i+1][j]));
			}
			if(i>1)
			{
				e[++top]=node(ex(i,j),ex(i-1,j),abs(mp[i][j]-mp[i-1][j]));
			}
			if(j<n){
				e[++top]=node(ex(i,j),ex(i,j+1),abs(mp[i][j]-mp[i][j+1]));
			}
			if(j>1)
			{
				e[++top]=node(ex(i,j),ex(i,j-1),abs(mp[i][j]-mp[i][j-1]));
			}
		}
	}
	sort(e+1,e+top+1,cmp);
	for(int i=1;i<=top;i++){
		int u=findf(e[i].x),v=findf(e[i].y);
		ll w=e[i].z;
		if(u!=v){
			size[u]+=size[v];
			jl[u]+=jl[v];
			fa[v]=u;
			size[v]=0;
			jl[v]=0;
			if(size[u]>=t)
			{
				ans=ans+jl[u]*w;
				jl[u]=0;
			}
		}
	}
	write(ans);
	puts("");
	return 0;
}
2021/11/8 21:50
加载中...