2019.2.19
长沙集训 $ Day 9 $
今天并没有什么新内容,所以我自学了图论中的重要算法——网络最大流
网络最大流:
给定一个网络图,求网络中的最大流量。
反向网络
求解网络流最为暴力的算法就是通过一遍遍 $ BFS $ 来寻找是否有一条流量不为零的链连接源点($ S T $),如果有就进行更新并计算答案。这条链就是所谓的增广路。
但这种方式有可能会走入错误的道路,如下图(网络图是有向图, $ 1 $ 为源点, $ 4 $ 为汇点)。
如果程序选择这条链为增广路,那计算出的最大流只有 $ 1 $ ,但实际最大流显然是 $ 2 $ 。该如何解决这个问题呢?其实很简单,那就是建立反向网络。(建立反向网络实际上是在原图中连反向边,这里为了表述清楚所以分开画图)
初始时反向网络的所有边流量上限都为 $ 0 $ ,当找到一条增广路进行更新时,将原网络中的边减少流量上限,给反向网络中的边增加流量上限。
这样,即使第一遍走了 $ 1 \to 2 \to 3 \to 4 $ 这条路径,第二遍 $ BFS $ 时依然可以找到 $ 1 \to 3 \to 2 \to 4 $ 这条增广路,完美解决了之前的问题。事实上,建立反向网络是网络流算法普遍使用的处理方式。
为什么这样做是对的呢?思考一下,走过刚刚的两条路径,实际上 $ 2 \to 3 $ 的路径上,流量上限仍未 $ 1 $ ,而 $ 3 \to 2 $ 路径的流量上限仍为 $ 0 $ 。相当于走了 $ 1 \to 2 \to 4 $ 和 $ 1 \to 3 \to 4 $ 这两条链。
$ E-K $ 算法
$ E-K $ 算法实际上就是上文说到的暴力 $ BFS $ ,每找到一条增广路就进行更新,复杂度极高,且容易被卡。
$ Dinic $ 算法
$ Dinic $ 算法应该是使用最多的网络流增广路算法,实际上是对 $ E-K $ 算法的优化,具体做法是增加了分层图的处理。先用一次 $ BFS $ 给网络图分层,之后用 $ DFS $ 搜索增广路,相比之前的 $ BFS $ 暴力,效率已有很大的提高。
$ Dinic $ 算法的最差时间复杂度为 $ O(n^{2} \cdot m) $ ,但其实算法大部分情况下的复杂度都远低于上限,且大部分网络流题目的图都比较小, $ n $ 基本上是 $ [10^{2} , 10^{3}] $ 之间,熟练使用 $ Dinic $ 算法便可应对大部分题目。
$ Dinic $ 算法程序
program project1;
const max_n=10005;
max_m=100005;
var
r,deep:array[0..max_n]of int64;
l,v,w:array[0..4*max_m]of int64;
n,m,s,t:longint;
function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;
function search(q:longint):longint;
begin
if q mod 2=0 then exit(q-1)
else exit(q+1);
end;
procedure re;
var i,t,x,y,z:longint;
begin
t:=0;
for i:=1 to m do begin
read(x,y,z);
inc(t);
l[t]:=r[x];
r[x]:=t;
v[t]:=y;
w[t]:=z;
inc(t);
l[t]:=r[y];
r[y]:=t;
v[t]:=x;
w[t]:=0;
end;
end;
function bfs:boolean;
var i,f,head,tail:longint;
p:array[0..6*max_m]of longint;
begin
fillchar(deep,sizeof(deep),0);
head:=0;
tail:=1;
deep[s]:=1;
p[tail]:=s;
while head<tail do begin
inc(head);
f:=p[head];
i:=r[f];
while i<>0 do begin
if (w[i]>0) and (deep[v[i]]=0) then begin
deep[v[i]]:=deep[f]+1;
inc(tail);
p[tail]:=v[i];
end;
i:=l[i];
end;
end;
if deep[t]=0 then exit(false)
else exit(true);
end;
function dfs(f,dis:int64):int64;
var i:longint;
begin
dfs:=0;
if f=t then exit(dis);
i:=r[f];
while i<>0 do begin
if (w[i]>0) and (deep[v[i]]=deep[f]+1) then dfs:=dfs(v[i],min(dis,w[i]));
if dfs>0 then begin
dec(w[i],dfs);
inc(w[search(i)],dfs);
exit(dfs);
end;
i:=l[i];
end;
exit(0);
end;
procedure main;
var ans,df:int64;
begin
ans:=0;
while bfs=true do begin
df:=dfs(s,maxint);
while df<>0 do begin
inc(ans,df);
df:=dfs(s,maxint);
end;
end;
writeln(ans);
end;
begin
read(n,m,s,t);
re;
main;
end.