| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
终于A了速度很慢
program poj1273;
const
maxn=300;
type
tt=array[1..maxn] of longint;
var
a,b:array[1..maxn,0..maxn] of int64;
n,m,i:longint;
x,y,d,f:int64;
function find(var pre:tt):longint;
var
d,bj:array[1..maxn] of longint;
l,r,now:longint;
begin
fillchar(d,sizeof(d),0);
fillchar(bj,sizeof(bj),0);
l:=0; r:=1; d[1]:=1; bj[1]:=1; pre[1]:=0;
while l<r do
begin
inc(l);
now:=d[l];
for i:=1 to n do
if (a[now,i]>0) and (bj[i]=0) then
begin
inc(r);
d[r]:=i;
bj[i]:=1;
pre[i]:=now;
if i=n then exit(1);
end;
end;
exit(0);
end;
function ford:integer;
var
pre:tt;
i:longint;
max:int64;
begin
fillchar(pre,sizeof(pre),0);
if find(pre)=0 then exit(0);
i:=n; max:=maxlongint;
while pre[i]<>0 do
begin
if a[pre[i],i]<max then max:=a[pre[i],i];
i:=pre[i];
end;
i:=n;
while pre[i]<>0 do
begin
a[pre[i],i]:=a[pre[i],i]-max;
a[i,pre[i]]:=a[i,pre[i]]+max;
i:=pre[i];
end;
f:=f+max;
end;
begin
while not(eof) do
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
readln(m,n);
for i:=1 to m do
begin
readln(x,y,d);
if x<>y then
begin
inc(b[x,0]);
b[x,b[x,0]]:=y;
a[x,y]:=a[x,y]+d;
end;
end;
f:=0;
while ford<>0 do;
writeln(f);
end;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator