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.

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。