记录编号	109034	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]滑雪场地的难度系数	最终得分	100
用户昵称	King	是否通过	通过
代码语言	C++	运行时间	2.188 s
提交时间	2014-07-07 16:16:58	内存使用	40.12 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define MAXN 600
struct road
{
	int x1,y1,x2,y2,d;
}ro[MAXN*MAXN*5];
const int dx[]={0,-1,1,0,0};
const int dy[]={0,0,0,-1,1};
typedef long long ll;
int a[MAXN][MAXN],n,m,ros,t,r[MAXN*MAXN],rs[MAXN*MAXN],zhi[MAXN*MAXN];
ll ans;
int root(int x)
{
	if(r[x]==x)return x;
	else r[x]=root(r[x]);
	return r[x];
}
void merge(int x,int y)
{
	rs[root(x)]+=rs[root(y)];
	r[root(y)]=root(x);
}
bool cmp(road x,road y){return x.d<y.d;}
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	memset(zhi,0xff,sizeof(zhi));
	scanf("%d%d%d",&n,&m,&t);
	rep(i,1,n*m)r[i]=i,rs[i]=1;
	rep(i,1,n)
		rep(j,1,m)scanf("%d",&a[i][j]);
	rep(i,1,n)
		rep(j,1,m)
			rep(k,1,n)
			{
				int x=i+dx[k],y=j+dy[k];
				if(x>0 && y>0 && x<=n && y<=m)
				{
					ros++;
					ro[ros].x1=i;ro[ros].y1=j;ro[ros].x2=x;ro[ros].y2=y;
					ro[ros].d=abs(a[x][y]-a[i][j]);
				}
			}
	sort(ro+1,ro+1+ros,cmp);
	rep(i,1,ros)
	{
		int u=(ro[i].x1-1)*m+ro[i].y1,v=(ro[i].x2-1)*m+ro[i].y2;
		if(root(u)!=root(v))
		{
			if(rs[root(u)]>=t && rs[root(v)]>=t)continue;
			if(rs[root(u)]>=t){zhi[root(v)]=ro[i].d;rs[root(v)]=t;continue;}
			if(rs[root(v)]>=t){zhi[root(u)]=ro[i].d;rs[root(u)]=t;continue;}
			merge(u,v);
			if(rs[root(u)]>=t)zhi[root(u)]=ro[i].d;
		}
	}
	rep(i,1,n*m)
	{
		int p;
		scanf("%d",&p);
		if(p)ans=ans+ll(zhi[root(i)]);
	}
	printf("%lld\n",ans);
	return 0;
}