ditch.pas

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

{
ID:maigoak1
PROG:ditch
}

program ditch;
const
  max=200;
var
  fin,fout:text;
  v1,v2:array[1..max]of byte;
  cap,flow:array[1..max]of longint;
  n,m,i:byte;
  ans:longint;
function min(a,b:longint):longint;
  begin
    if a<b then min:=a else min:=b;
  end;
procedure maxflow;
  var
    l:array[1..max]of integer;
    i,j:byte;
    more:boolean;
    d:longint;
  begin
    fillchar(flow,sizeof(flow),0);
    repeat
      fillchar(l,sizeof(l),0);
      l[1]:=maxint;
      repeat
        more:=false;
        for i:=1 to n do
          if (l[v1[i]]<>0) and (l[v2[i]]=0) and (flow[i]<cap[i]) then begin
            more:=true;l[v2[i]]:=i;if l[m]<>0 then break;
          end
          else if (l[v2[i]]<>0) and (l[v1[i]]=0) and (flow[i]>0) then begin
            more:=true;l[v1[i]]:=-i;if l[m]<>0 then break;
          end;
      until not more or (l[m]<>0);
      if l[m]<>0 then begin
        i:=m;d:=maxlongint;
        repeat
          j:=i;if l[i]>0 then i:=v1[l[i]] else i:=v2[-l[i]];
          if l[j]>0 then
            d:=min(d,cap[l[j]]-flow[l[j]])
          else
            d:=min(d,flow[-l[j]]);
        until i=1;
        i:=m;
        repeat
          j:=i;if l[i]>0 then i:=v1[l[i]] else i:=v2[-l[i]];
          if l[j]>0 then
            inc(flow[l[j]],d)
          else
            dec(flow[-l[j]],d);
        until i=1;
      end;
    until l[m]=0;
  end;
begin
  assign(fin,'ditch.in');
  reset(fin);
  readln(fin,n,m);
  for i:=1 to n do
    readln(fin,v1[i],v2[i],cap[i]);
  close(fin);

  maxflow;

  ans:=0;
  for i:=1 to n do
    if v1[i]=1 then inc(ans,flow[i]);

  assign(fout,'ditch.out');
  rewrite(fout);
  writeln(fout,ans);
  close(fout);
end.