《网络传输问题》解题报告

大榕树 \ 信息学奥赛 \ 解题报告

《网络传输问题》解题报告

原文链接：http://www.mydrs.org/program/list.asp?id=296
本题的要求是求出信息封包传递到目标计算机的最段时间，考虑到实际传输中很可能出现圈的情况，所以不适合使用树的模式或者深度搜索，适合采用广度搜索，因此本题编程的难度并不大。
首先，考虑广度搜索中每个节点的的状态，我们考虑这样记录
Type Max = 80;
       Sptr = ^Stype;
Stype = Record
              Id : 1..Max;     {记录每个节点所处计算机编号}
              H : set of 1..Max; {记录扩展到该节点的时候，信息封包已经取得的验证集合}
              Next : Sptr      {后向指针}
       End;
Var S : Sptr；
经过这样的考虑，我们能够很快地完成初步的编程，但很明显，这样做是不够的，因为作为广度扩展，状态数量会以几何倍增长，所以必须加以截肢。我们可以这样考虑。
A ：在第n次扩展中，信息从计算机a传递到计算机b，在第n+1次扩展中，信息若试图再次传递回计算机a，则要考虑，经过b的时候，是否信息封包从计算机b上取得通过其他某计算机所需要的身份验证，若无，则此次操作将无意义，应截掉。
B ：在第n次扩展中，扩展出节点Sp，比较该节点所取得的身份验证集合与之前所有扩展到相同计算机的所有节点的身份验证集合，若Sp.h包含于St.h{节点t为先前已经扩展出来的节点，且Sp.id=St.id}，则考虑截去节点Sp。
经过这样简单的处理，状态总数将大大减少，虽然这样会影响速度，却只有这样才能达到题目的要求。且经过这样的处理，对于样例数据甚至不用考虑使用指针，用数组就足够完成。样例程序如下：
program network5;
const inputfile       = 'network.in5';
       outputfile      = 'network.out';
       max             = 80;
       maxsave         = 4000;
type stype           = record id:byte;h:set of 1..max; end;
var   w               : array [1..max,1..max] of boolean;
       m               : array [1..max] of byte;
       s               : array [1..maxsave] of stype;
       y               : array [1..max] of boolean;
       n,op,en,e,t,ti : longint;
       i,j,k           : longint;
       ty              : set of 1..max;
label out,finish;
begin
   assign(input,inputfile); reset(input);
   assign(output,outputfile); rewrite(output);
   readln(n); fillchar(w,sizeof(w),false); fillchar(y,sizeof(y),false);
   for i:=1 to n do
     begin
       read(m[i]); if m[i]<>0 then y[m[i]]:=true;
       while not eoln do begin read(j); w[i,j]:=true; w[j,i]:=true; end;
     end;
   op:=1; en:=1; s[1].id:=1; s[1].h:=[]; t:=en; e:=en; ti:=0;
   repeat inc(ti);
     for i:=op to en do
       for j:=1 to n do if w[s[i].id,j] then
         if (m[j]=0)or(m[j] in s[i].h) then
           begin
             ty:=s[i].h; if y[j] then ty:=ty+[j];
             for k:=1 to e do if (s[k].id=j)and(ty*s[k].h=ty) then goto out;
             for k:=e+1 to t do if s[k].id=j then
               if s[k].h*ty=ty then goto out else
               if s[k].h*ty=s[k].h then begin s[k].h:=ty; goto out; end;
             if j=n then begin writeln(ti); goto finish; end;
             inc(t); s[t].id:=j; s[t].h:=ty; out:;
           end;
     e:=t; op:=en+1; en:=t;
   until op>en;
   finish:begin close(input); close(output); end;
end.

作者：杨晨醒
来源：福建师大附中
时间：2001-12-14

上一篇：《破译密码》解题报告
下一篇：《小球钟》解题报告