实现功能:同最大流 1
这里面主要是把前面的邻接矩阵改成了邻接表,相比之下速度大大提高——本人实测,当M=1000000 N=10000 时,暂且不考虑邻接矩阵会不会MLE,新的程序速度快了很多倍(我们家这个很弱的电脑上耗时0.3s);而当M=300000 N=10000时,优势更加明显(几乎是秒出),别的没了,尤其当遇到稀疏图的时候这样子是大大划算的!!!
1 type
2 point=^node;
3 node=record
4 g,w:longint;
5 next:point;
6 end;
7
8 var
9 i,j,k,l,m,n,tmp,ans,aug,mi,s,t:longint;
10 di,a:array[0..10005] of point;
11 pre,his,dis,vh:array[0..10005] of longint;
12 flag:boolean;p,jl:point;
13 function min(x,y:longint):longint;inline;
14 begin
15 if x<y then min:=x else min:=y;
16 end;
17 function add(x,y,z:longint):longint;inline;
18 var p:point;
19 begin
20 new(p);p^.w:=z;p^.g:=y;
21 p^.next:=a[x];a[x]:=p;
22 end;
23 procedure op(x,y,z:longint);inline;
24 var p:point;
25 begin
26 p:=a[x];
27 while p<>nil do
28 begin
29 if (p^.g=y) and ((p^.w+z)>=0) then
30 begin
31 p^.w:=p^.w+z;
32 break;
33 end;
34 p:=p^.next;
35 end;
36 end;
37 begin
38 readln(n,m,s,t);
39 for i:=1 to n do a[i]:=nil;
40 for i:=1 to m do
41 begin
42 readln(j,k,l);
43 add(j,k,l);add(k,j,0);
44 end;
45 for i:=1 to n do di[i]:=a[i];
46 fillchar(dis,sizeof(dis),0);
47 fillchar(pre,sizeof(pre),0);
48 fillchar(his,sizeof(his),0);
49 fillchar(vh,sizeof(vh),0);
50 i:=s;vh[0]:=n;ans:=0;aug:=maxlongint;
51 while dis[s]<n do
52 begin
53 flag:=false;his[i]:=aug;
54 p:=a[i];
55 while p<>nil do
56 begin
57 if (p^.w>0) and (dis[i]=(dis[p^.g]+1)) then
58 begin
59 aug:=min(aug,p^.w);
60 pre[p^.g]:=i;di[i]:=p;
61 flag:=true;i:=p^.g;
62 if i=t then
63 begin
64 ans:=ans+aug;
65 while i<>s do
66 begin
67 tmp:=i;
68 i:=pre[i];
69 op(i,tmp,-aug);
70 op(tmp,i,aug);
71 end;
72 aug:=maxlongint;
73 end;
74 break;
75 end;
76 p:=p^.next;
77 end;
78 if flag then continue;
79 jl:=nil;mi:=n-1;
80 p:=a[i];
81 while p<>nil do
82 begin
83 if (p^.w>0) and (dis[p^.g]<mi) then
84 begin
85 jl:=p;mi:=dis[p^.g];
86 end;
87 p:=p^.next;
88 end;
89 di[i]:=jl;
90 dec(vh[dis[i]]);
91 if vh[dis[i]]=0 then break;
92 dis[i]:=mi+1;
93 inc(vh[dis[i]]);
94 if i<>s then
95 begin
96 i:=pre[i];
97 aug:=his[i];
98 end;
99 end;
100 writeln(ans);
101 end.
102