NOIP-2013-车站分级-解题报告

NOIP-2013-车站分级-解题报告 (浏览次数：42)

huaidan

发表于2013/11/28 9:02:00

发下我写的普及组第四题“车站分级”的丑陋代码（前面3个题目太水了），看了浙江PJ的成绩，干掉这个题目的孩子就只有宁波蛟川书院的一个牛，我的孩子写的也不好，超时一个点，可惜了点，平时练习的时候做过这种类型的题目，考场里面写的不够优秀，哎！不过还是要为嘉怡姐威武一下，390分！浙江赛区第一名！

【解题思路】：主要的就是拓扑排序记录层次数就是答案，具体实现的话首先构造有向图g[low[j],hight[k]]，期中low[j]表示某趟火车从a车站到b车站途中没有停的车站，hight[k]表示某趟火车从a车站到b车站途中必停的车站，由低low[j]→hight[k]构造有向图，结合边表效率要高的！具体实现详见下面的伪代码！希望路过的神牛批评指正！

program level;
const maxn=1005;
var n,m,ans:longint;
      hash:array[0..maxn] of boolean;
      low,hight,f,opt:array[0..maxn] of longint;
     g:array[0..maxn,0..maxn] of longint;
     vis:array[0..maxn,0..maxn] of boolean;
procedure init;
var i,j,k,len,x,min,max:longint;
   begin
    assign(input,'level.in');reset(input);
      assign(output,'level.out');rewrite(output);
     readln(n,m);
      fillchar(g,sizeof(g),0);
      fillchar(f,sizeof(f),0);//存储入度
      fillchar(vis,sizeof(vis),false);//标记有向图由low→hight
       for i:=1 to m do
       begin
           fillchar(hash,sizeof(hash),false);//标记经过时必停的车站
           fillchar(low,sizeof(low),0);//存储经过但没停的车站编号
           fillchar(hight,sizeof(hight),0);//存储经过时必停的车站编号
           read(len);
         for j:=1 to len do
             begin
               read(x);
             if j = 1 then min:=x;
             if j = len then max:=x;
             hash[x]:=true;
             inc(hight[0]);
               hight[hight[0]]:=x;
           end;
           readln;
          for j:=min to max do
             if not hash[j] then begin
                                             inc(low[0]);
                                             low[low[0]]:=j;
                                         end;
         for j:=1 to low[0] do//构造有向图，由low[j]→hight[k]，为下面的拓扑做准备
           for k:=1 to hight[0] do
             if not vis[low[j],hight[k]] then begin
                                                              vis[low[j],hight[k]]:=true;//采用布尔类型标记是否构造过
                                                              inc(g[low[j],0]);
                                                             g[low[j],g[low[j],0]]:=hight[k];//边表存储
                                                             inc(f[hight[k]]);//往hight[k]这点上+一个入度
                                                      end;
       end;
   end;
procedure main;
var i,j,head,tail,num:longint;
   begin
     fillchar(opt,sizeof(opt),0);//队列存储入度为0的节点
     head:=1;tail:=0;
     ans:=0;num:=n;
     while num <> 0 do
       begin
         inc(ans);//拓扑记录层次数
         for i:=1 to n do//扫描入度为0的节点
           if f[i] = 0 then begin
                                     f[i]:=-1;dec(num);
                                     inc(tail);opt[tail]:=i;
                                 end;
         for i:=head to tail do//从opt[i]点开始边表扫描
           for j:=1 to g[opt[i],0] do
             dec(f[g[opt[i],j]]);
         head:=tail+1;
       end;
   end;
procedure print;
begin
    write(ans);
    close(input);close(output);
end;
begin
init;
main;
print;
end.

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。