比赛 |
20140418 |
评测结果 |
C |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
0 |
用户昵称 |
隨風巽 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2014-04-18 11:25:42 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cstring>
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;
}