POJ 1273(网络流-附hllp+sap模板）

网络流入门题目

Program P1273;
Var
   n,m,i,j,x,y,p,level:longint;
   map,f:array[1..400,1..400] of longint;
   list:array[0..400,0..400] of longint;
   queue:array[1..400] of longint;
   b:array[1..400] of boolean;
   d,e:array[1..400] of longint;
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 dijstra;
var
   h,t,i:longint;
begin
   queue[1]:=n;
   b[n]:=true;
   h:=1;
   t:=1;
   while h<=t do
   begin
      for i:=1 to n-1 do
         if (map[i,queue[h]]>0) and (not(b[i])) then
         begin
            inc(t);
            queue[t]:=i;
            b[i]:=true;
            d[i]:=d[queue[h]]+1;
         end;
      inc(h);
   end;
   d[1]:=n+1;
end;
procedure push(i,j:longint);
var
   flow:longint;
begin
   flow:=min(map[i,j]-f[i,j],e[i]);

   if (e[j]=0) and (j<>1) and (j<>n) then
   begin
      inc(list[d[j],0]);
      list[d[j],list[d[j],0]]:=j;
      level:=max(level,d[j]);
   end;

   dec(e[i],flow);
   inc(e[j],flow);
   inc(f[i,j],flow);
   f[j,i]:=-f[i,j];
end;
procedure relable(i:longint);
var
   j,minj:longint;
begin
   minj:=maxlongint;
   for j:=1 to n do
      if (map[i,j]-f[i,j]>0) and (b[j]) then
         minj:=min(minj,d[j]);
   d[i]:=minj+1;

   level:=d[i];
   list[level,0]:=1;
   list[level,1]:=i;
end;
procedure sa;
var
   i,j,minj:longint;
   tag:boolean;
begin
   dijstra;
   level:=0;
   for i:=1 to n do
      if (map[1,i]>0) and (b[i]) then
      begin
         dec(e[1],map[1,i]);
         inc(e[i],map[1,i]);
         inc(f[1,i],map[1,i]);
         f[i,1]:=-f[1,i];
         inc(list[d[i],0]);
         list[d[i],list[d[i],0]]:=i;
         level:=max(level,d[i]);
      end;
   while (level>0) do
   begin
      i:=list[level,list[level,0]];
      dec(list[level,0]);
      while (level>0) and (list[level,0]=0) do dec(level);

      for j:=1 to n do
         if (map[i,j]-f[i,j]>0) and (d[i]=d[j]+1) and (b[j]) then
         begin
            push(i,j);
            if e[i]=0 then break;
         end;
      if e[i]>0 then relable(i);
   end;
end;
begin
   while not eof do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(f,sizeof(f),0);
      fillchar(d,sizeof(d),0);
      fillchar(b,sizeof(b),false);
      fillchar(list,sizeof(list),0);
      fillchar(e,sizeof(e),0);
      readln(m,n);
      for i:=1 to m do
      begin
         readln(x,y,p);
         inc(map[x,y],p);
      end;
      sa;
      writeln(e[n]);
   end;
end.