比赛 20140418 评测结果 C
题目名称 滑雪场地的难度系数 最终得分 0
用户昵称 超级傲娇的AC酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2014-04-18 11:26:45
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; 
int M,N;
vector<vector<pair<int,int> > >Map;
int Prim(int,int,int);
int main()
{int T,i,j,A[510][510];
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	cin>>M>>N>>T;
	Map.resize(M*N);
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
			cin>>A[i][j];
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
		{
			if(i+1<M)Map[i*N+j].push_back(make_pair(abs(A[i+1][j]-A[i][j]),(i+1)*N+j));
			if(j+1<M)Map[i*N+j].push_back(make_pair(abs(A[i][j+1]-A[i][j]),(i)*N+j+1));
			if(i>0)Map[i*N+j].push_back(make_pair(abs(A[i-1][j]-A[i][j]),(i-1)*N+j));
			if(j>0)Map[i*N+j].push_back(make_pair(abs(A[i][j-1]-A[i][j]),(i)*N+j+1));
		}
	int Ans=0;
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
		{Ans+=Prim(M*N,i*N+j,T);}
	cout<<Ans;
	return 0;
}

int Prim(int Len,int pos,int T)
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
	bool v[Len];int i;pair<int,int>Node;int Ans=0;
	for(i=0;i<Len;i++)
		v[i]=false;
	Q.push(make_pair(pos,0));
	while(!Q.empty())
	{
		Node=Q.top();
		Q.pop();
		if(v[Node.second]==false)
		{
			Ans=min(Ans,Node.first);v[Node.second]=true;
			T--;
			if(T==0)return Ans;
			for(i=0;i<Map[Node.second].size();i++)
				if(v[Map[Node.second][i].second]==false)
					Q.push(Map[Node.second][i]);
		}
	}
}
/*
int bfs(int Px,int Py)
{
	vector<vector<bool> >B;
	deque<pair<int,int> >pos;
	int i;
	pos.push_back(make_pair(Px,Py));
	while(!pos.empty())
	{
		for(i=0;i<4;i++)
		{
			posx=pos[i].first+Means[i][0];
			posy=pos[i].second+Means[i][0];
			if(posx>=0&&posx<M)
				if(posx>=0&&posy<N)
					if(B[posx][posy]==false)
					{
						
						//B[posx][posy]=true;
						//pos.push_back(make_pair(posx,posy));////////////////
						//T--;
						//if(T==0)
							//return ans;
					}
		}
		pos.pop_back();
	}
}
*/