实现功能:同之前
可以看见的是这次的程序优美了许多,代码简短了一倍还多,可是速度却是和原来的邻接表一个级别的(在Codevs上面草地排水那题的运行时间比较,但是显然数据很大时应该比那个慢些),原理差不多,感觉dfs里面的来回倒变量很神奇
1 var
2 s,t,i,j,k,l,m,n,ans:longint;
3 a:array[0..1000,0..1000] of longint;
4 d,dv:array[0..10000] of longint;
5 function min(x,y:longint):longint;inline;
6 begin
7 if x<y then min:=x else min:=y;
8 end;
9 function dfs(x,flow:longint):longint;inline;
10 var i,j,k,l:longint;
11 begin
12 if x=t then exit(flow);
13 dfs:=0;
14 for i:=1 to n do
15 if (a[x,i]>0) and (d[x]=(d[i]+1)) then
16 begin
17 k:=dfs(i,min(flow-dfs,a[x,i]));
18 dec(a[x,i],k);
19 inc(a[i,x],k);
20 inc(dfs,k);
21 if dfs=flow then exit;
22 end;
23 if d[s]=n then exit;
24 dec(dv[d[x]]);
25 if dv[d[x]]=0 then d[s]:=n;
26 inc(d[x]);
27 inc(dv[d[x]]);
28 end;
29 begin
30 readln(n,m,s,t);
31 fillchar(a,sizeof(a),0);
32 for i:=1 to m do
33 begin
34 readln(j,k,l);
35 inc(a[j,k],l);
36 end;
37 fillchar(d,sizeof(d),0);
38 fillchar(dv,sizeof(dv),0);
39 dv[0]:=n;ans:=0;
40 while d[s]<n do inc(ans,dfs(s,maxlongint));
41 writeln(ans);
42 end.