首页 > 代码库 > USACO2014JAN滑雪场评级GOLDT3
USACO2014JAN滑雪场评级GOLDT3
3. 滑雪场评级{ Gold题3}
【问题描述】
滑雪场用一个M*N(1 <= M,N <= 500)的数字矩阵表示海拔高度，每个数字表示一个范围在0 .. 1,000,000,000的高度。有些格子被指定为起点，组织者想对这些起点做难度评级。
如果起点P点是一个难度级别为D的起点，则D必须是满足以下条件的一个最小值：
（1）从一个格子只能滑到相邻的格子；
（2）这两个格子的海拔差不超过D；
（3）至少能够到达T（1 <= T <= M*N）个格子（包括起点本身）。
【文件输入】
第一行，三个用空格隔开的整数，分别表示M，N和T。
接下来2.. M+1行，每行一个N个整数，表示海拔。
接下来M+2.. 2M+1行，每行一个整数0或者1，其中1表示该格子是一个起点。
【文件输出】
共一行，一个整数，所有起点的难度和。
【输入样例】
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
【输出样例】
24
【样例说明】
左上角的格子是一起点，难度为4，右下角的格子是一个起点，难度为20。
（learning from MY）
把每个点和他的右边点和下面点建一条边。
绝对值之差即为边的权值。
按边的权值从小到大排序。
然后按顺序加边，合并每条边的两个端点所在的集合。
合并的过程中同时建图。
如果原来集合里的点数小于t合并后大于等于t，则该集合中所有的起点的难度就应该是刚刚加入的边的权值，累加答案。
我们需要用一个DFS来处理这个“新晋”集合，（即找到所有的起点，并累加答案）
因为并查集记录的只有父亲节点还有这个集合的结点数，所以我们就需要以上的建图过程。
（容易证明在这个类似贪心的过程中我们得到的每一个起点难度都是最优的答案）
const px:array[1..2] of integer=(0,1);py:array[1..2] of integer=(1,0);var h:array[0..250001,0..20] of longint;n,m,x,i,t,j:longint;sum,ans:int64;hh,num:array[0..501,0..501] of longint;pd,visit:array[0..250000] of boolean;size,father,u,v,w:array[0..500000] of longint;procedure qsort(a,b:longint);var i,j,temp,x:longint;begini:=a;j:=b;x:=w[(i+j) div 2];repeatwhile w[i]<x do inc(i);while w[j]>x do dec(j);if i<=j thenbegintemp:=w[i];w[i]:=w[j];w[j]:=temp;temp:=u[i];u[i]:=u[j];u[j]:=temp;temp:=v[i];v[i]:=v[j];v[j]:=temp;inc(i);dec(j);end;until i>j;if i<b then qsort(i,b);if a<j then qsort(a,j);end;procedure dfs(k,p:longint);var i:longint;beginvisit[k]:=true;if pd[k] thenbeginans:=ans+p;pd[k]:=false;end;for i:=1 to h[k,0] doif not visit[h[k,i]] then dfs(h[k,i],p);end;function can(a,b:longint):boolean;beginif (a<=m) and (b<=n) thenexit(True);exit(false);end;function getfather(k:longint):longint;var tip:longint;beginif father[k]=k then exit(k);tip:=father[k];father[k]:=getfather(tip);getfather:=father[k];end;function check:longint;var temp,i,t1,t2,j,k:longint;beginfor i:=1 to n*m dobeginfather[i]:=i;size[i]:=1;end;for i:=1 to sum dobegint1:=getfather(u[i]);t2:=getfather(v[i]);if t1<>t2 then begin //如果他们不在同一个集合中，那么需要合并if (size[t1]<t) and (size[t1]+size[t2]>=t) then dfs(t1,w[i]); //如题解所述累加答案if (size[t2]<t) and (size[t1]+size[t2]>=t) then dfs(t2,w[i]);father[t2]:=t1;size[t1]:=size[t1]+size[t2]; //合并以后的集合的结点数即为两个集合相加inc(h[u[i],0]); //建图h[u[i],h[u[i],0]]:=v[i];inc(h[v[i],0]);h[v[i],h[v[i],0]]:=u[i];end;end;end;procedure build;var i,j,k:longint;beginfor i:=1 to m dofor j:=1 to n dobeginfor k:=1 to 2 doif can(i+px[k],j+py[k]) thenbegininc(sum);u[sum]:=num[i,j];v[sum]:=num[i+px[k],j+py[k]];w[sum]:=abs(hh[i,j]-hh[i+px[k],j+py[k]]); //建边end;end;end;beginassign(input,‘skilevel.in‘);assign(output,‘skilevel.out‘);reset(input);rewrite(output);readln(m,n,t);for i:=1 to m dofor j:=1 to n dobeginread(hh[i,j]);num[i,j]:=n*(i-1)+j;end;for i:=1 to m dofor j:=1 to n dobeginread(x);if x=1 then pd[num[i,j]]:=true;end;build;qsort(1,sum);check;writeln(ans);close(input);close(output);end.
USACO2014JAN滑雪场评级GOLDT3