记录编号	158878	评测结果	AAAAAAAAAAAA
题目名称	草地排水	最终得分	100
用户昵称	hjt	是否通过	通过
代码语言	Pascal	运行时间	0.003 s
提交时间	2015-04-18 11:28:25	内存使用	0.34 MiB

program grass;
const inf=100000;
type node=record
       flow,cap,fr,tt:longint;
     end;
var ed:array[0..405]of node;
    vis:array[0..205]of boolean;
    q,d,cur:array[0..300]of longint;
    map:array[0..205,0..205]of longint;
    i,x,y,z,n,m,head,tail,cnt:longint;

function min(x,y:longint):longint;
begin
  if x<y then exit(x)
  else exit(y);
end;

procedure addedge(x,y,z:longint);
begin
  inc(cnt);
  ed[cnt].fr:=x;
  ed[cnt].tt:=y;
  ed[cnt].cap:=z;
  inc(map[x,0]);
  map[x,map[x,0]]:=cnt;
  inc(cnt);
  ed[cnt].fr:=y;
  ed[cnt].tt:=x;
  inc(map[y,0]);
  map[y,map[y,0]]:=cnt;
end;

procedure init;
begin
  readln(n,m);
  cnt:=-1;
  for i:=1 to n do
    begin
      readln(x,y,z);
      addedge(x,y,z);
    end;
end;

function bfs:boolean;
var u,j:longint;e:node;
begin
  fillchar(q,sizeof(q),0);
  fillchar(vis,sizeof(vis),0);
  head:=1;
  tail:=1;
  q[1]:=1;
  d[1]:=0;
  vis[1]:=true;
  while head<=tail do
    begin
      u:=q[head];
      inc(head);
      for j:=1 to map[u,0] do
        begin
          e:=ed[map[u,j]];
          if not(vis[e.tt]) and (e.flow<e.cap) then
            begin
              inc(tail);
              q[tail]:=e.tt ;
              d[e.tt]:=d[u]+1;
              vis[e.tt]:=true;
            end;
        end;
    end;
  exit(vis[m]);
end;

function dfs(s,a:longint):longint;
var j,flow,f,t:longint;e:node;
begin
  if (s=m) or (a=0) then exit(a);
  flow:=0;
  t:=cur[s]+1;
  for j:=t to map[s,0] do
    begin
      if (d[ed[map[s,j]].fr]+1=d[ed[map[s,j]].tt]) then
        begin
          f:=dfs(ed[map[s,j]].tt,min(a,ed[map[s,j]].cap-ed[map[s,j]].flow));
          if (f>0) then
            begin
              inc(ed[map[s,j]].flow,f);
              dec(ed[map[s,j] xor 1].flow,f);
              dec(a,f);
              inc(flow,f);
              if a=0 then break;
            end;
        end;
      cur[s]:=j;
    end;
  exit(flow);
end;

function maxflow(s,t:longint):longint;
var ans:longint;
begin
  ans:=0;
  while bfs do
    begin
      fillchar(cur,sizeof(cur),0);
      ans:=ans+dfs(s,inf);
    end;
  exit(ans);
end;

begin
  assign(input,'ditch.in');
  assign(output,'ditch.out');
  reset(input);
  rewrite(output);
  fillchar(ed,sizeof(ed),0);
  init;
  writeln(maxflow(1,m));
  close(input);
  close(output);
end.