记录编号	97285	评测结果	AETETETETT
题目名称	[USACO Jan14]滑雪场地的难度系数	最终得分	10
用户昵称	隨風巽	是否通过	未通过
代码语言	C++	运行时间	5.371 s
提交时间	2014-04-18 11:35:07	内存使用	1.97 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXMN=250+10;
struct node{int num,dist;};
struct cmp2{bool operator()(node a, node b){return a.dist>b.dist;}};
vector<int>sx,sy;
struct Edge{int u,v,w;};
vector<Edge>edges;
int M,N,T,h[MAXMN][MAXMN];
long long int ans=0;
inline int ID(int i,int j){return (i-1)*N+j;}
bool cmp(Edge a,Edge b){return a.w<b.w;}
int max(int a,int b){return a>b?a:b;}
struct Kruskal
{
	vector<int>g[MAXMN*MAXMN],w[MAXMN*MAXMN];
	int i,p[MAXMN*4];
	void PRETREATMENT(void)
	{for(i=0;i<edges.size();i++)p[i]=i;}
	int FIND(int x)
	{return p[x]==x?x:p[x]=FIND(p[x]);}
	void SORT(void)
	{
		int i,u,v,s=0;
		PRETREATMENT();
		sort(edges.begin(),edges.end(),cmp);
		for(i=0;i<edges.size();i++)   
		{
			u=FIND(edges[i].u);
			v=FIND(edges[i].v);
		    if(u!=v)
		    {
				s++;
				p[u]=v;
				u=edges[i].u;v=edges[i].v;
				g[u].push_back(v);w[u].push_back(edges[i].w);
				g[v].push_back(u);w[v].push_back(edges[i].w);
				if(s==M*N-1)break;
			}
		}
	}
	priority_queue<node,vector<node>,cmp2>q;
	node u;
	int s,maxcost,n;
	bool entered[MAXMN*MAXMN];
	void BFS(int v)
	{
		q.push((node){v,0});
		memset(entered,0,sizeof(entered));
		entered[v]=true;
		maxcost=s=0;
		while(!q.empty())
		{
			u=q.top();
			q.pop();
			s++;
			maxcost=max(maxcost,u.dist);
			if(s==T){ans+=maxcost;return;}
			n=g[u.num].size();
			for(i=0;i<n;i++)
			{
				v=g[u.num][i];
				if(not entered[v])
				{
					q.push((node){v,w[u.num][i]});
					entered[v]=true;
				}
			}
		}
	}
};
Kruskal MST;
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	scanf("%d%d%d",&M,&N,&T);
	int i,j,x;
	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
			scanf("%d",&h[i][j]);
	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
		{
			scanf("%d",&x);
			if(x==1){sx.push_back(i);sy.push_back(j);}
		}
	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
		{
			if(i+1<=M)edges.push_back((Edge){ID(i,j),ID(i+1,j),abs(h[i][j]-h[i+1][j])});
			if(j+1<=N)edges.push_back((Edge){ID(i,j),ID(i,j+1),abs(h[i][j]-h[i][j+1])}); 
		}
	MST.SORT();
	for(i=0;i<sx.size();i++)
		MST.BFS(ID(sx[i],sy[i]));
	cout<<ans<<endl;
	return 0;
}