SAP算法:求最大流有一種經典的算法，就是每次找增廣路時用BFS找，保證找到的增廣路是弧數最少的，也就是所謂的Edmonds-Karp算法。
基本介紹
- 中文名：sap算法
- 別名：Edmonds-Karp算法
- 優點：時間複雜度低
- 重要最佳化：鄰接表最佳化等
簡介,算法介紹,代碼實現,重要最佳化,鄰接表最佳化,GAP最佳化,當前弧最佳化,
簡介
可以證明的是在使用最短路增廣時增廣過程不超過V*E次，每次BFS的時間都是O(E)，所以Edmonds-Karp的時間複雜度就是O(V*E^2)。
算法介紹
如果能讓每次尋找增廣路時的時間複雜度降下來，那么就能C了，使用距離標號的最短增廣路算法就是這樣的。所謂距離標號，就是某個點到匯點的最少的弧的數量（另外一種距離標號是從源點到該點的最少的弧的數量，本質上沒什麼區別）。設點i的標號為D[i]，那么如果將滿足D[i]=D[j]+1的弧(i,j)叫做允許弧，且增廣時只走允許弧，那么就可以達到“怎么走都是最短路”的效果。每個點的初始標號可以在一開始用一次從匯點沿所有反向邊的BFS求出，實踐中可以初始設全部點的距離標號為0，問題就是如何在增廣過程中維護這個距離標號。
維護距離標號的方法是這樣的：當找增廣路過程中發現某點出發沒有允許弧時，將這個點的距離標號設為由它出發的所有弧的終點的距離標號的最小值加一。這種維護距離標號的方法的正確性我就不證了。由於距離標號的存在，由於“怎么走都是最短路”，所以就可以採用DFS找增廣路，用一個棧保存當前路徑的弧即可。當某個點的距離標號被改變時，棧中指向它的那條弧肯定已經不是允許弧了，所以就讓它出棧，並繼續用棧頂的弧的端點增廣。還有一種在常數上有所最佳化的寫法是改變距離標號時把當前弧設為那條提供了最小標號的弧。當前弧的寫法之所以正確就在於任何時候我們都能保證在鄰接表中當前弧的前面肯定不存在允許弧。
還有一個常數最佳化是在每次找到路徑並增廣完畢之後不要將路徑中所有的頂點退棧，而是只將瓶頸邊以及之後的邊退棧，這是借鑑了Dinic算法的思想。注意任何時候待增廣的“當前點”都應該是棧頂的點的終點。這的確只是一個常數最佳化，由於當前邊結構的存在，我們肯定可以在O(n)的時間內復原路徑中瓶頸邊之前的所有邊。
代碼實現
var
flag:boolean;
jl,min,flow,aug,j,m,n,tmp,a,b,c,i:longint;
his,pre,dis,vh,di:array[0..1024] of longint;
map:array[1..1024,1..1024] of longint;
begin
readln(m,n);
for i:=1 to m do
begin
readln(a,b,c);
inc(map[a,b],c);
end;
vh[0]:=n;
for i:=1 to n do di[i]:=1;{當前弧初始為第一條弧}
i:=1;{從S開始搜}
aug:=maxlongint;
while dis[1]<n do
begin
his[i]:=aug;{標記，以便以後返回這個值}
flag:=false;{這個是是否有找到允許弧的標誌}
for j:=di[i] to n do{從當前弧開始搜}
begin
if (map[i,j]>0)and(dis[j]+1=dis[i]) then{找到允許弧}
begin
flag:=true;
di[i]:=j;{標記當前弧}
if map[i,j]<aug then aug:=map[i,j];
pre[j]:=i;{記錄前驅}
i:=j;
if i=n then{找到增廣路}
begin
inc(flow,aug);
while i<>1 do
begin
tmp:=i;
i:=pre[i];
dec(map[i,tmp],aug);
inc(map[tmp,i],aug);
end;
aug:=maxlongint;
end;
break;{找到允許弧則退出查找}
end;
end;
if flag then continue;{找到允許弧}
min:=n-1;{沒有允許弧了，需要重標號}
for j:=1 to n do
begin
if (map[i,j]>0)and(dis[j]<min) then
begin
jl:=j;
min:=dis[j];
end;
end;
di[i]:=jl;
dec(vh[dis[i]]);{GAP最佳化}
if vh[dis[i]]=0 then break;
dis[i]:=min+1;
inc(vh[dis[i]]);
if i<>1 then
begin
i:=pre[i];{返回上一層}
aug:=his[i];{知道之前記錄這個值的用處了吧}
end;
end;
write(flow);
end.
重要最佳化
鄰接表最佳化
如果頂點多的話，往往N^2存不下，這時候就要存邊：
存每條邊的出發點，終止點和價值，然後排序一下，再記錄每個出發點的位置。以後要調用從出發點出發的邊時候，只需要從記錄的位置開始找即可（其實可以用鍊表）。優點是時間加快空間節省，缺點是編程複雜度將變大，所以在題目允許的情況下，建議使用鄰接矩陣。
GAP最佳化
如果一次重標號時，出現距離斷層，則可以證明ST無可行流，此時則可以直接退出算法。
當前弧最佳化
為了使每次找增廣路的時間變成均攤O(V)，還有一個重要的最佳化是對於每個點保存“當前弧”：初始時當前弧是鄰接表的第一條弧；在鄰接表中查找時從當前弧開始查找，找到了一條允許弧，就把這條弧設為當前弧；改變距離標號時，把當前弧重新設為鄰接表的第一條弧。
