ac1267.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1267;
const
  maxn=50;
var
  want,from,v,mark:array[0..maxn]of byte;
  offer:array[0..maxn,1..maxn]of integer;
  n,e,i,j,k,x,y,ans:longint;
  r:real;
procedure find_cycle(m:byte);
  var
    c,t:longint;
  procedure shrink;
    var
      x,a,i:byte;
    begin
      x:=v[c];
      repeat
        a:=v[c];t:=offer[from[a],a];inc(ans,t);
        for i:=0 to n do if offer[i,a]-t<offer[i,x] then offer[i,x]:=offer[i,a]-t;
        for i:=1 to n do if offer[a,i]<offer[x,i] then offer[x,i]:=offer[a,i];
        want[a]:=0;
        dec(c);
      until v[c]=x;
      want[x]:=1;

      for i:=1 to n do if want[from[i]]=0 then from[i]:=x;
      from[x]:=0;
      for i:=1 to n do
        if (want[i]>0) and (i<>x) and (offer[i,x]<offer[from[x],x]) then
          from[x]:=i;
    end;
  begin
    c:=0;v[0]:=m;mark[m]:=m;
    repeat
      inc(c);v[c]:=from[v[c-1]];
      if mark[v[c]]=0 then mark[v[c]]:=m
        else if mark[v[c]]=m then shrink
        else exit;
    until false;
  end;
begin
  want[0]:=1;
  repeat
    fillchar(offer,sizeof(offer),127);
    read(n);e:=0;
    for i:=1 to n do begin
      read(r,want[i]);
      offer[0,i]:=round(r*10);
    end;
    read(k);
    for i:=1 to k do begin
      read(x,y,r);
      offer[x,y]:=round(r*10);
    end;

    ans:=0;
    fillchar(from,sizeof(from),0);
    for i:=1 to n do
      if want[i]>0 then begin
        for j:=1 to n do
          if (want[j]>0) and (offer[j,i]<offer[from[i],i]) then from[i]:=j;
        inc(ans,offer[from[i],i]*(want[i]-1));
      end;

    fillchar(mark,sizeof(mark),0);mark[0]:=99;
    for i:=1 to n do
      if mark[i]=0 then
        find_cycle(i);
    for i:=1 to n do
      if want[i]>0 then inc(ans,offer[from[i],i]);
    writeln(ans/10:0:2);
  until seekeof;
end.