记录编号	97379	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]滑雪场地的难度系数	最终得分	100
用户昵称	◆半城烟沙灬為你打天下	是否通过	通过
代码语言	C++	运行时间	0.539 s
提交时间	2014-04-18 19:07:17	内存使用	13.23 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
struct sky
{
	int ff,tt,ww;
};
sky c[500005];
int father[500005],size[500005],a[500005];
int n,m,t;
int num[505][505];
long long ans[500005],tot1,tot2;
int abc(int x)
{
	return x<0?-x:x;
}
int find(int x)
{
	return x==father[x]?x:find(father[x]);
}
void merge(int x,int y,int z)
{
	if (size[x]>size[y]) swap(x,y);
	if (size[y]<t&&size[x]+size[y]>=t) ans[y]=z;
	else 
	if (size[x]<t&&size[x]+size[y]>=t) ans[x]=z;
	father[x]=y;
	size[y]+=size[x];
}
long long ask(int x)
{
	while (ans[x]==-1&&father[x]!=x) x=father[x];
	return ans[x]==-1?0:ans[x];
}
bool comp(sky a,sky b)
{
	return a.ww<b.ww;
}
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	int ch,fx,fy;
	scanf("%d%d%d",&n,&m,&t);
	tot1=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&ch);
			num[i][j]=++tot1;
			a[tot1]=ch;
		}
	tot2=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			if (i<n)
			{
				tot2++;
				c[tot2].ff=num[i][j];
				c[tot2].tt=num[i+1][j];
				c[tot2].ww=abc(a[num[i][j]]-a[num[i+1][j]]);
			}
			if (j<m)
			{
				tot2++;
				c[tot2].ff=num[i][j];
				c[tot2].tt=num[i][j+1];
				c[tot2].ww=abc(a[num[i][j]]-a[num[i][j+1]]);
			}
		}
	sort(c+1,c+tot2+1,comp);
	for (int i=1;i<=tot1;i++)
	{
		father[i]=i;
		size[i]=1;
		ans[i]=-1;
	}
	for (int i=1;i<=tot2;i++)
	{
		fx=find(c[i].ff);
		fy=find(c[i].tt);
		if (fx!=fy) merge(fx,fy,c[i].ww);
	}
	long long tot=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&ch);
			if (ch)
			{
				tot+=ask(num[i][j]);
			}
		}
	printf("%lld\n",tot);
	return 0;
}