POJ 1459(预留推进)

内容目录

hllp写到最后写成预留推进了……

Program P1459;
var
   n,np,nc,m,i,j,src,t,level:longint;
   ch:char;
   s:string;
   d,e,pre:array[-1..100] of longint;
   map,f:array[-1..100,-1..100] of longint;
   queue:array[1..102] of longint;
   list:array[0..103,0..102] of longint;
   b:array[-1..100] of boolean;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure hllp;
var
   i,j,maxflow,flow,minj:longint;
   h,t:longint;
   tag:boolean;
begin
   level:=0;
   maxflow:=0;
   flow:=0;
   h:=1;
   t:=1;
   queue[h]:=n;
   while h<=t do
   begin
      for i:=0 to n-1 do
         if (map[i,queue[h]]>0) and (not(b[i])) then
         begin
            inc(t);
            queue[t]:=i;
            d[i]:=d[queue[h]]+1;
            b[i]:=true;
         end;
      inc(h);
   end;
   d[-1]:=n+2;
   {
   for i:=0 to n-1 do
      if e[i]>0 then
      begin
         inc(list[d[i],0]);
         list[d[i],list[d[i],0]]:=i;
         level:=max(level,d[i]);
      end;
   }
   while (true) do
   begin
      i:=n;
      for j:=0 to n-1 do
      begin
         if (e[j]>0) and (d[j]>d[i]) then i:=j;
      end;
      if i=n then break;
 {     i:=list[level,list[level,0]];
      dec(list[level,0]);
      while (level>0) and (list[level,0]=0) do dec(level);
      }

      tag:=false;
      for j:=-1 to n do
      begin
         if e[i]=0 then break;
            if (d[i]=d[j]+1) and (map[i,j]-f[i,j]>0) then
            begin
               tag:=true;
               flow:=min(map[i,j]-f[i,j],e[i]);
               dec(e[i],flow);
               inc(e[j],flow);
               inc(f[i,j],flow);
               f[j,i]:=-f[i,j];
            end;
      end;
      if (e[i]>0) then
      begin
         minj:=maxlongint;
         for j:=-1 to n do
            if (map[i,j]-f[i,j]>0) {and (d[i]>=d[j])} then minj:=min(minj,d[j]);
        { if minj=maxlongint then
         begin
            e[i]:=0;
            continue;
         end;    }
         d[i]:=minj+1;
      end;

   end;

end;
function isdight(a:char):boolean;
begin
   if (48<=ord(a)) and (ord(a)<=57) then exit(true) else exit(false);
end;
procedure rea(var a:longint);
var
   ch:char;
   s:string;
begin
   ch:=' ';
   while not(isdight(ch)) do read(ch);
   s:='';
   repeat
      s:=s+ch;
      read(ch);
   until not(isdight(ch));
   val(s,a);
end;
begin
{   assign(input,'p1459.in');
   assign(output,'p1459.out');
   reset(input);
   rewrite(output);                    }
   while not seekeof do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(e,sizeof(e),0);
      fillchar(f,sizeof(f),0);
      fillchar(list,sizeof(list),0);
      fillchar(d,sizeof(d),0);
      fillchar(b,sizeof(b),false);
      rea(n);
      for i:=-1 to n do pre[i]:=i;
      rea(np);
      rea(nc);
      rea(m);
      for i:=1 to m do
      begin
        rea(src);
        rea(t);
        rea(map[src,t]);
      end;
      for i:=1 to np do
      begin
        rea(t);
        rea(map[-1,t]);
        e[t]:=map[-1,t];
        f[-1,t]:=map[-1,t];
        f[t,-1]:=-map[-1,t];
      end;
      for i:=1 to nc do
      begin
         rea(src);
         rea(map[src,n]);
      end;

      hllp;
      writeln(e[n]);
   end;
{   close(input);
   close(output);     }
end.