mouse.pas

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

program mouse_test;
type
  tp=array[1..3,1..2] of integer;
  tr=array[1..200] of tp;
  tt=array[1..200] of integer;
  bj=array[1..200] of byte;
const in_f='mouse.dat';out_f='mouse.out';
var
  cave:tr;
  cave_num,edge,move,result:tt;
  mark:bj;
  f:text;
  i,n,now_max,temp_max,max:integer;
  bb:boolean;

procedure input;
var i,j,k,L,x,y,temp:integer;
begin

  assign(f,in_f);
  reset(f);

  fillchar(cave_num,sizeof(cave_num),0);
  fillchar(cave,sizeof(cave),0);
  max:=0;

  readln(f,n);
  for i:=1 to (3*n) div 2 do
  begin
    readln(f,x,cave[x,cave_num[x]+1,1],cave[x,cave_num[x]+1,2]);
    max:=max+cave[x,cave_num[x]+1,2];
    temp:=cave[x,cave_num[x]+1,2];
    inc(cave_num[x]);

    y:=x;x:=cave[x,cave_num[x],1];
    cave[x,cave_num[x]+1,1]:=y;
    cave[x,cave_num[x]+1,2]:=temp;
    inc(cave_num[x]);

    max:=max+temp;
  end;
  fillchar(mark,sizeof(mark),0);
  fillchar(edge,sizeof(edge),0);

  close(f);
end;

procedure find(m:integer);	{搜索过程}
var i,j,mark_break:byte;
begin
  if temp_max>=now_max then
    exit;

  if m=n+1 then
  begin
    if (cave[move[n],1,1]=1) or (cave[move[n],2,1]=1) or (cave[move[n],3,1]=1) then
    begin
      for i:=1 to 3 do
        if (cave[move[n],i,1]=1) then
        begin
          now_max:=temp_max+cave[move[n],i,2];
          break;
        end;
      result:=move;
    end;
    exit;
  end;

  for i:=1 to 3 do
    if mark[cave[move[m-1],i,1]]=0 then
    begin
      move[m]:=cave[move[m-1],i,1];
      mark[move[m]]:=1;

      mark_break:=0;
      for j:=1 to 3 do
      begin
        inc(edge[cave[move[m-1],j,1]]);
        bb:=(cave[1,1,1]=cave[move[m-1],j,1]) or (cave[1,2,1]=cave[move[m-1],j,1]) or (cave[1,3,1]=cave[move[m-1],j,1]);
        if (bb and  (mark[cave[move[m-1],j,1]]=0) and (edge[cave[move[m-1],j,1]]>2))
         or ((not bb) and (mark[cave[move[m-1],j,1]]=0) and (edge[cave[move[m-1],j,1]]>1)) then
          mark_break:=1;	{判断是否会无路可走}
      end;

      temp_max:=temp_max+cave[move[m-1],i,2];
      if (mark_break=0) and
      ((mark[cave[1,1,1]]+mark[cave[1,2,1]]+mark[cave[1,3,1]]<=2) or (n=m)) then
        find(m+1);
      temp_max:=temp_max-cave[move[m-1],i,2];

      mark[move[m]]:=0;

      for j:=1 to 3 do	{将相邻的边都减一}
        dec(edge[cave[move[m-1],j,1]]);
      move[m]:=0;

    end;
end;

begin
  input;

  now_max:=0;temp_max:=0;
  move[1]:=1;
  mark[1]:=1;
  now_max:=max+1;
  find(2);

  assign(f,out_f);
  rewrite(f);

  { writeln(f,now_max); }
  for i:=1 to n-1 do
    write(f,result[i],' ');
  writeln(f,result[n]);

  close(f);
end.