温存's Blog

uses
        math;
type
	{node_st=record
		p,t:longint;
	end;}
	arr_st=array[1..1000000]of longint;
var
	st:arr_st;
	R,G:array[1..1000,1..1000]of longint;
	tot,s,t,edges,best:longint;
function beside(st:arr_st;node:longint):boolean;
var
  i:longint;
begin
	for i:=1 to tot do
	begin
		if st[i]=node then exit(true);
	end;
	exit(false);
end;

function getmini(st:arr_st):longint;
var
	i:longint;
begin
	i:=1;
	getmini:=R[st[1]][st[2]];
	while (st[i+1]<>0)do
	begin
	  getmini:=min(R[st[i]][st[i+1]],getmini);
    inc(i);
	end;
  exit(getmini);
end;


function aug(node:longint;var st:arr_st):boolean;
var
  i:longint;
  flag,geta:boolean;
begin
  if node=t then
	begin
    inc(tot);
		st[tot]:=0;
		exit(true);
	end;
  flag:=false;
	for i:=1 to edges do
	begin
		if (R[node][i]>0)and(not beside(st,i)) then
		begin
      flag:=true;
			inc(tot);
			st[tot]:=i;
			geta:=aug(i,st);
		end;
    if geta then exit(true);
	end;
  if flag=false then
    st[tot]:=0;
  dec(tot);
	if node = s then
  begin
  	 fillchar(st,sizeof(st),0);
  	 exit(false);
  end;
end;

procedure change(num:longint);
var
	i:longint;
begin
	i:=1;
	while (st[i+1]<>0)do
	begin
		dec(R[st[i]][st[i+1]],num);
    inc(i);
	end;
end;
procedure solve;
var
	b:boolean;
  mini:longint;
begin
	repeat
    tot:=1;
    fillchar(st,sizeof(st),0);
    st[1]:=s;
    b:=aug(s,st);
		mini:=getmini(st);
		change(mini);
    inc(best,mini);
	until not b;
end;

procedure init;
var
	i,cap,x,y:longint;
begin
	readln(s,t,edges);
	fillchar(R,sizeof(R),0);
	fillchar(G,sizeof(G),0);
	for i:=1 to edges do
	begin
		readln(x,y,cap);
		G[x][y]:=cap;
		inc(R[x][y],cap);
	end;
end;

begin
  assign(input,'ms.in');
  assign(output,'ms.out');
  reset(input);
  rewrite(output);
	init;
	solve;
	writeln(best);
  close(input);
  close(output);
end.