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

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<fstream>
#include<iostream>
using namespace std;
int M,N,T,H[510][510];
int tot,next[250001]={0},head[250001],tail[250001],label[510][510];
int ufs[250001],size[250001];
int ans[250001]={0},dealt=0,start_sum=0;
long long Ans=0;
bool did[250001]={false};
class edge
{
public:
	int u,v,w;
};
vector <edge> E;
bool operator < (edge a,edge b){return a.w<b.w;}
int Find(int x){return ufs[x]==x?x:ufs[x]=Find(ufs[x]);}
void deal(int x,int weight)
{
	if(did[x])return;
	for(int y=head[x];y>0;y=next[y])
	{
		if(!ans[y])
		{
			dealt++;
			Ans+=(long long)weight;
			ans[y]=weight;
		}
	}
	did[x]=true;
}
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	scanf("%d%d%d",&M,&N,&T);
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
		{
			scanf("%d",&H[i][j]);
		}
	int temp;
	tot=0;
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
		{
			label[i][j]=++tot;
			ufs[label[i][j]]=label[i][j];
			size[label[i][j]]=1;
			scanf("%d",&temp);
			if(temp)
			{
				head[label[i][j]]=tail[label[i][j]]=label[i][j];
				start_sum++;
			}
			else
			{
				head[label[i][j]]=tail[label[i][j]]=-1;
			}
		}
	for(int i=1;i<=M;i++)
		for(int j=1;j<N;j++)
			E.push_back((edge){label[i][j],label[i][j+1],abs(H[i][j]-H[i][j+1])});
	for(int i=1;i<M;i++)
		for(int j=1;j<=N;j++)
			E.push_back((edge){label[i][j],label[i+1][j],abs(H[i][j]-H[i+1][j])});
	sort(E.begin(),E.end());
	int v1,v2,w;
	for(unsigned int i=0;i<E.size() && dealt<start_sum;i++)//Kruskal
	{
		v1=Find(E[i].u);v2=Find(E[i].v);w=E[i].w;
		if(v1==v2)continue;
		if(head[v1]==-1)swap(v1,v2);
		if(size[v1]+size[v2]>=T)
		{
			deal(v1,w);
			deal(v2,w);
		}
		size[v1]+=size[v2];
		if(head[v2]!=-1)next[tail[v1]]=head[v2],tail[v1]=tail[v2];
		ufs[v2]=v1;
	}
	printf("%lld\n",Ans);
	return 0;
}