实现功能:同sap网络最大流
今天第一次学Dinic,感觉最大的特点就是——相当的白话,相当的容易懂,而且丝毫不影响复杂度,顶多也就是代码长个几行
主要原理就是每次用spfa以O(n)的时间复杂度预处理出层次图,然后像sap一样深搜一下,搞定。。。代码相当好懂
1 type
2 point=^node;
3 node=record
4 g,w:longint;
5 next,anti:point;
6 end;
7 var
8 i,j,k,l,m,n,s,t,ans:longint;
9 a:array[0..10000] of point;
10 c,d:array[0..10000] of longint;
11 function min(x,y:longint):longint;
12 begin
13 if x<y then min:=x else min:=y;
14 end;
15 procedure add(x,y,z:longint);
16 var p:point;
17 begin
18 new(p);p^.g:=y;p^.w:=z;p^.next:=a[x];a[x]:=p;
19 new(p);p^.g:=x;p^.w:=0;p^.next:=a[y];a[y]:=p;
20 a[x]^.anti:=a[y];a[y]^.anti:=a[x];
21 end;
22 function spfa:boolean; //spfa预处理出层次图,同时检测连通性
23 var p:point;f,r:longint;
24 begin
25 fillchar(c,sizeof(c),255);
26 d[1]:=s;f:=1;r:=2;c[s]:=0;
27 while f<r do
28 begin
29 p:=a[d[f]];
30 while p<>nil do
31 begin
32 if (p^.w<>0) and (c[p^.g]=-1) then
33 begin
34 c[p^.g]:=c[d[f]]+1;
35 d[r]:=p^.g;
36 inc(r);
37 end;
38 p:=p^.next;
39 end;
40 inc(f);
41 end;
42 exit(c[t]<>-1);
43 end;
44 function dfs(x,flow:longint):longint; //像sap一样的DFS么么哒
45 var p:point;k:longint;
46 begin
47 if x=t then exit(flow);
48 dfs:=0;p:=a[x];
49 while p<>nil do
50 begin
51 if (p^.w<>0) and ((c[x]+1)=c[p^.g]) then
52 begin
53 k:=dfs(p^.g,min(flow-dfs,p^.w));
54 if p^.w<>maxlongint then dec(p^.w,k);
55 if p^.anti^.w<>maxlongint then inc(p^.anti^.w,k);
56 inc(dfs,k);if dfs=flow then exit;
57 end;
58 p:=p^.next;
59 end;
60 end;
61 begin
62 readln(m,n);s:=1;t:=n;
63 for i:=s to t do a[i]:=nil;
64 for i:=1 to m do
65 begin
66 readln(j,k,l);
67 add(j,k,l);
68 end;
69 ans:=0;
70 while spfa do inc(ans,dfs(s,maxlongint));
71 writeln(ans);
72 readln;
73 end.