USACO 4.2 ditch Drainage Ditches 程序

TASK: ditch LANG: PASCAL

Compiling… Compile: OK

Executing… Test 1: TEST OK

\[0.011 secs, 364 KB\]

Test 2: TEST OK

\[0.000 secs, 364 KB\]

Test 3: TEST OK

\[0.000 secs, 368 KB\]

Test 4: TEST OK

\[0.000 secs, 368 KB\]

Test 5: TEST OK

\[0.000 secs, 368 KB\]

Test 6: TEST OK

\[0.011 secs, 364 KB\]

Test 7: TEST OK

\[0.011 secs, 364 KB\]

Test 8: TEST OK

\[0.000 secs, 364 KB\]

Test 9: TEST OK

\[0.000 secs, 364 KB\]

Test 10: TEST OK

\[0.000 secs, 368 KB\]

Test 11: TEST OK

\[0.000 secs, 364 KB\]

Test 12: TEST OK

\[0.000 secs, 368 KB\]

All tests OK. Your program (‘ditch’) produced all correct answers! This is your submission #5 for this problem. Congratulations!

{ ID:ceeji PROB:ditch LANG:PASCAL } //By Ceeji //Date: 2009-4-18 //Type: Network Flow //Source: Ditch //State: Programming Program ditch; Const maxn=200; fin=‘ditch.in’; fou=‘ditch.out’; Var m,n,i,p,q,ci,ans,j:longint; c:array

\[1..maxn,1..maxn\]

of longint; f,a,d:array

\[1..maxn\]

of longint; b:array

\[1..maxn\]

of boolean; Function min(a,b:longint):longint; begin if a>b then exit(b) else exit(a); end;

Procedure init; begin assign(input,fin); reset(input); assign(output,fou); rewrite(output); fillchar(c,sizeof(c),0); readln(n,m); for i:=1 to n do begin readln(p,q,ci); inc(c

\[p,q\]

,ci); end; close(input); ans:=0; end;

Function doit:boolean; var i,k:longint; begin i:=1; j:=2; d

\[1\]

:=1; fillchar(f,sizeof(f),0); fillchar(b,sizeof(b),0); a

\[1\]

:=maxlongint; f

\[1\]

:=0; repeat for k:=1 to m do begin if (c

\[d\[i\]

,k]>0)and(b

\[k\]

=false) then begin d

\[j\]

:=k; f

\[j\]

:=i; a

\[j\]

:=min(a

\[i\]

,c

\[d\[i\]

,k]); b

\[k\]

:=true; inc(j); if k=m then exit(true); end; end; inc(i); until i>=j; exit(false); end;

Procedure doit2; var i,k:longint; begin i:=j-1; while i<>1 do begin dec(c

\[d\[f\[i\]

],d

\[i\]

],a

\[j-1\]

); inc(c

\[d\[i\]

,d

\[f\[i\]

]],a

\[j-1\]

); i:=f

\[i\]

; end; inc(ans,a

\[j-1\]

); end;

begin init; while doit do doit2; writeln(ans); close(output); end.