const
  maxn=210;
  inf=1000000000;

type
  edge=record
    point,front,lim:longint;
  end;

var
  e:array[0..maxn*2] of edge;
  head,cur,mark,q:array[0..maxn] of longint;
  n,m,cnt,i,x,y,z,maxflow:longint;

function min(x,y:longint):longint; inline;
begin
  if x>y then min:=y else min:=x;
end;

procedure addedge(x,y,z:longint); inline;
begin
  inc(cnt); e[cnt].point:=y; e[cnt].lim:=z; e[cnt].front:=head[x]; head[x]:=cnt;
end;

function bfs:boolean;
var
  i,h,t,u,p,po:longint;
begin
  for i:=2 to n do mark[i]:=0;
  h:=1; t:=1; q[1]:=1; mark[1]:=1;
  while h<=t do
    begin
      u:=q[h]; p:=head[u]; cur[u]:=p;
      while p>-1 do
        begin
          po:=e[p].point;
          if (mark[po]=0) and (e[p].lim>0)
            then
              begin
                mark[po]:=mark[u]+1;
                inc(t); q[t]:=po;
              end;
          p:=e[p].front;
        end;
      inc(h);
    end;
  if mark[n]=0 then exit(false) else exit(true);
end;

procedure dinic(k,sum:longint);
var
  p,po,temp:longint;
begin
  if k=n then begin inc(maxflow,sum); exit; end;
  if mark[k]=mark[n] then exit;
  p:=cur[k];
  while (p>-1) and (sum>0) do
    begin
      po:=e[p].point;
      if (mark[po]=mark[k]+1) and (e[p].lim>0)
        then
          begin
            temp:=maxflow;
            dinic(po,min(sum,e[p].lim));
            temp:=maxflow-temp;
            dec(e[p].lim,temp);
            inc(e[p xor 1].lim,temp);
            dec(sum,temp);
          end;
      cur[k]:=p; p:=e[p].front;
    end;
  if sum>0 then cur[k]:=-1;
end;

begin
  while not eof do
    begin
      readln(m,n);
      cnt:=-1;
      for i:=1 to n do head[i]:=-1;
      for i:=1 to m do
        begin
          readln(x,y,z);
          addedge(x,y,z);
          addedge(y,x,0);
        end;

      maxflow:=0;
      while bfs do dinic(1,inf);

      writeln(maxflow);
    end;
end.

• Re:pascal (36) jinzhihan 2016-08-18 21:05:22
  • Re:pascal (7) jinzhihan 2016-08-18 21:05:40
    • Re:pascal (11) hncsyjc 2016-08-18 21:06:16