比赛 |
20140418 |
评测结果 |
AAAAAAAAAA |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
100 |
用户昵称 |
cstdio |
运行时间 |
0.503 s |
代码语言 |
C++ |
内存使用 |
8.26 MiB |
提交时间 |
2014-04-18 09:27:37 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<list>
using namespace std;
typedef long long ll;
ll ans=0;
const int SIZEn=510,SIZEN=500*500+10;
int n,m,T;//n行m列
int height[SIZEn][SIZEn]={0};
vector<int> Plis;
int Psize=0;
int issrc[SIZEn][SIZEn]={0};
int ufs[SIZEN]={0};
int size[SIZEN]={0};
int next[SIZEN]={0};
int head[SIZEN]={0};
int tail[SIZEN]={0};
int maxw[SIZEN]={0};
bool det[SIZEN]={0};
int surenum=0;
class EDGE{
public:
int from,to,w;
};
bool operator < (EDGE a,EDGE b){
return a.w<b.w;
}
vector<EDGE> edges;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int hash(int x,int y){
return x*m+y;
}
void decide(int a,int w){
if(det[a]) return;
if(head[a]==-1) return;
for(int x=head[a];x!=-1;x=next[x]){
ans+=w,surenum++;
}
det[a]=true;
}
int grand(int x){
return ufs[x]==-1?x:ufs[x]=grand(ufs[x]);
}
void print(int x){
cout<<"("<<x/m<<","<<x%m<<")";
}
void merge(int a,int b,int w){
//cout<<a<<" "<<b<<" "<<size[a]<<" "<<size[b]<<" "<<w<<endl;
//cout<<"sb";
if(head[a]==-1) swap(a,b);
//print(a);print(b);cout<<size[a]<<" "<<size[b]<<" "<<w<<endl;
//如果链表一个空一个非空,那么空的是b
if(size[a]+size[b]>=T){
//cout<<a<<" "<<b<<" "<<size[a]<<" "<<size[b]<<endl;
decide(a,w);
decide(b,w);
}
//cout<<"s";
size[a]=size[a]+size[b];
maxw[a]=w;//从小往大加,w一定是当前最大的
if(head[b]!=-1) next[tail[a]]=head[b],tail[a]=tail[b];
ufs[b]=a;
//cout<<"b";
}
void work(void){
if(T==1){
printf("%d\n",0);
return;
}
for(int i=0;i<Plis.size();i++){
head[Plis[i]]=tail[Plis[i]]=i;
}
sort(edges.begin(),edges.end());
int i=0;
//Psize=1;
while(surenum<Psize&&i<edges.size()){
EDGE &e=edges[i++];
int ga=grand(e.from),gb=grand(e.to);
//cout<<e.from<<" "<<e.to<<" "<<e.w<<endl;
//cout<<ga<<" "<<gb<<" "<<e.w<<endl;
if(ga!=gb) merge(ga,gb,e.w);
//cout<<e.w<<" "<<size[grand(0)]<<endl;
}
printf("%lld\n",ans);
}
void read(void){
//memset(size,-1,sizeof(size));
//cout<<size[10]<<endl;
memset(ufs,-1,sizeof(ufs));
memset(next,-1,sizeof(next));
memset(head,-1,sizeof(head));
memset(tail,-1,sizeof(tail));
//memset(size,1,sizeof(next));
scanf("%d%d%d",&n,&m,&T);
for(int i=0;i<n*m;i++) size[i]=1;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&height[i][j]);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&issrc[i][j]);
if(issrc[i][j]){
Plis.push_back(hash(i,j));
Psize++;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<2;k++){
int ni=i+dx[k],nj=j+dy[k];
if(ni<0||ni>n-1||nj<0||nj>m-1) continue;
//cout<<i<<" "<<j<<" "<<ni<<" "<<nj<<endl;
edges.push_back((EDGE){hash(i,j),hash(ni,nj),abs(height[i][j]-height[ni][nj])});
}
}
}
}
int main(){
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
read();
work();
return 0;
}