tour.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 82 行

{
ID:maigoak1
PROG:tour
}

program tour;
const
  maxcities=100;
type
  vlist=set of 1..maxcities;
var
  fin,fout:text;
  city:array[1..maxcities]of string;
  adj:array[1..maxcities,1..maxcities]of boolean;
  count:array[1..maxcities,1..maxcities]of integer;
  visit:array[1..maxcities,1..maxcities]of vlist;
  n,j,k,n1,n2,t,max:byte;
  v,i:integer;
  s:string;
function citynum(s:string):byte;
  var
    i:byte;
  begin
    for i:=1 to n do
      if s=city[i] then begin
        citynum:=i;
        exit;
      end;
  end;
begin
  fillchar(city,sizeof(city),0);
  fillchar(adj,sizeof(adj),0);
  assign(fin,'tour.in');
  reset(fin);
  readln(fin,n,v);
  for i:=1 to n do
    readln(fin,city[i]);
  for i:=1 to v do begin
    readln(fin,s);
    t:=pos(' ',s);
    n1:=citynum(copy(s,1,t-1));n2:=citynum(copy(s,t+1,length(s)-t));
    if n1>n2 then begin t:=n1;n1:=n2;n2:=t;end;
    adj[n1,n2]:=true;
  end;
  close(fin);

  fillchar(count,sizeof(count),0);
  count[1,1]:=1;visit[1,1]:=[1];
  for i:=1 to n do
    for j:=1 to n do begin
      if i=j then continue;
      for k:=1 to j-1 do
        if count[i,k]>0 then
          if adj[k,j] then
            if not (j in visit[i,k]) then
              if count[i,k]+1>count[i,j] then begin
                count[i,j]:=count[i,k]+1;
                visit[i,j]:=visit[i,k]+[j];
              end;
      for k:=1 to i-1 do
        if count[k,j]>0 then
          if adj[k,i] then
            if not (i in visit[k,j]) then
              if count[k,j]+1>count[i,j] then begin
                count[i,j]:=count[k,j]+1;
                visit[i,j]:=visit[k,j]+[i];
              end;
    end;

  max:=1;
  for i:=1 to n-1 do
    if adj[i,n] then begin
      if count[i,n]>max then max:=count[i,n];
      if count[n,i]>max then max:=count[n,i];
    end;

  assign(fout,'tour.out');
  rewrite(fout);
  writeln(fout,max);
  close(fout);
end.