记录编号	97289	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]滑雪场地的难度系数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.485 s
提交时间	2014-04-18 11:37:36	内存使用	8.26 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<list>
using namespace std;
typedef long long ll;
ll ans=0;
const int SIZEn=510,SIZEN=500*500+10;
int n,m,T;//n行m列
int height[SIZEn][SIZEn]={0};
vector<int> Plis;
int Psize=0;
int issrc[SIZEn][SIZEn]={0};
int ufs[SIZEN]={0};
int size[SIZEN]={0};
int next[SIZEN]={0};
int head[SIZEN]={0};
int tail[SIZEN]={0};
int maxw[SIZEN]={0};
bool det[SIZEN]={0};
int surenum=0;
class EDGE{
public:
	int from,to,w;
};
bool operator < (EDGE a,EDGE b){
	return a.w<b.w;
}
vector<EDGE> edges;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int hash(int x,int y){
	return x*m+y;
}
void decide(int a,int w){
	if(det[a]) return;
	if(head[a]==-1) return;
	for(int x=head[a];x!=-1;x=next[x]){
		ans+=w,surenum++;
	}
	det[a]=true;
}
int grand(int x){
	return ufs[x]==-1?x:ufs[x]=grand(ufs[x]);
}
void print(int x){
	cout<<"("<<x/m<<","<<x%m<<")";
}
void merge(int a,int b,int w){
	if(head[a]==-1) swap(a,b);
	//如果链表一个空一个非空,那么空的是b
	if(size[a]+size[b]>=T){
		decide(a,w);
		decide(b,w);
	}
	size[a]=size[a]+size[b];
	maxw[a]=w;//从小往大加,w一定是当前最大的
	if(head[b]!=-1) next[tail[a]]=head[b],tail[a]=tail[b];
	ufs[b]=a;
}
void work(void){
	if(T==1){
		printf("%d\n",0);
		return;
	}
	for(int i=0;i<Plis.size();i++){
		head[Plis[i]]=tail[Plis[i]]=i;
	}
	sort(edges.begin(),edges.end());
	int i=0;
	while(surenum<Psize&&i<edges.size()){
		EDGE &e=edges[i++];
		int ga=grand(e.from),gb=grand(e.to);
		if(ga!=gb) merge(ga,gb,e.w);
	}
	printf("%lld\n",ans);
}
void read(void){
	memset(ufs,-1,sizeof(ufs));
	memset(next,-1,sizeof(next));
	memset(head,-1,sizeof(head));
	memset(tail,-1,sizeof(tail));
	scanf("%d%d%d",&n,&m,&T);
	for(int i=0;i<n*m;i++) size[i]=1;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&height[i][j]);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&issrc[i][j]);
			if(issrc[i][j]){
				Plis.push_back(hash(i,j));
				Psize++;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int k=0;k<2;k++){
				int ni=i+dx[k],nj=j+dy[k];
				if(ni<0||ni>n-1||nj<0||nj>m-1) continue;
				edges.push_back((EDGE){hash(i,j),hash(ni,nj),abs(height[i][j]-height[ni][nj])});
			}
		}
	}
}
int main(){
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	read();
	work();
	return 0;
}