2019.2.20
长沙集训 $ Day 10 $
昨天已经对网络流最大流有所了解,并且已经能够使用几种基本算法解题。虽然 $ Dinic $ 算法可以解决大部分问题,但如果遇到 $ n,m $ 较大的情况,还是需要更为优秀的算法。
网络最大流(加强版):
相较于普通版的最大流,本题的 $ n $ 有所减小,但 $ m $ 却增加了 $ 20000 $ ,并且出题人显然制作了针对普通 $ Dinic $ 的数据,所以我们需要更为快速的算法。
$ ISAP $ 算法
$ ISAP $ 算法是对普通 $ Dinic $ 的进一步优化,该算法先进行一次 $ BFS $ ,找出各节点到 $ T $ 的深度,之后在进行 $ DFS $ 搜索增广路径更新流量,同时更新深度,如果出现断层就结束算法。
更新节点深度:如果后续节点传回该节点的消耗总流量比当前节点可用流量上限小,即 $ flow_n<dis $ ,则该节点在此高度已无法做出贡献,就将该节点的高度提高 $ 1 $ 。
断层:如果某一深度(该深度小于 $ n $ )没有节点,则视为出现断层,此时残量网络中已不存在增广路,结束算法。
$ ISAP $ 算法的优点是只需运行一边 $ BFS $ ,无需为网络图重新分层,所以能极大加快处理速度。
$ HLPP $ 算法
实际上 $ ISAP $ 仍无法通过这道毒瘤题,我们看到了题目中所写的“预流推进”。我们之前所说的算法都是基于增广路进行扩展,而预流推进则类似手动模拟网络流的方式,先将所有的流量尽可能推给后续节点,如果流量超额,再通过反向网络推回。但直接这样进行推进可能会出现两个节点将流量互相-i推给对方,直到 $ TLE $ 为止。所以我们需要给每个节点标号,标号为 $ h_i $ 的节点只能将流量推给标号 $ h_i-1 $ 的节点,当一个节点存在超额流无法推出,就将其标号设为与其相连结点的最小标号+ $ 1 $ ,并将其压入队列,队列为空时结束算法。
为了加快速度,我们一般先从 $ T $ 开始进行一遍 $ BFS $ ,对节点进行预标号。同时如果处理过程中发现 $ h_i $ 的标号没有节点,那么此时标号比 $ h_i $ 高的节点就全部无法做出贡献,将它们的标号设为 $ n+1 $ 。
以上是普通预流推进算法,而 $ HLPP $ 中最高标号的意思就是:每次从队列中取出标号最高的节点进行处理,这样做的时间复杂度接近 $ O(n^{2} \cdot \sqrt m) $ ,在 $ n $ 较小而 $ m $ 很大时有很高的效率。
各种算法的时间复杂度
虽然 $ HLPP $ 的理论时间复杂度比 $ Dinic $ 低,但因为 $ Dinic $ 处理随机图时的复杂度远低于上限,而 $ HLPP $ 的复杂度基本都在最高复杂度附近,所以在数据较小时 $ HLPP $ 与 $ Dinic $ 的速度并无太大差别。
$ HLPP $ 程序
program project1;
type tp=record
h,pos:longint;
end;
const max_n=1205;
max_m=120005;
max_int=1061109567;
var
flow:array[0..2*max_n]of int64;
r,h,num:array[0..2*max_n]of longint;
tf:array[0..max_n]of boolean;
l,v,w:array[0..2*max_m]of longint;
heap:array[0..2*max_n]of longint;
n,m,s,t,tot:longint;
function min(a,b:longint):longint;
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:longint;
t,x,y,z:int64;
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;
procedure insert(pos:longint);
var i,j:longint;
t:longint;
begin
inc(tot);
heap[tot]:=pos;
i:=tot;
while (i shr 1)<>0 do begin
j:=i shr 1;
if h[heap[i]]>h[heap[j]] then begin
t:=heap[i];
heap[i]:=heap[j];
heap[j]:=t;
end
else break;
i:=j;
end;
end;
procedure del;
var i,j:longint;
t:longint;
begin
heap[1]:=heap[tot];
dec(tot);
i:=1;
while (i shl 1)<=tot do begin
j:=i shl 1;
if (j+1<=tot) and (h[heap[j+1]]>h[heap[j]]) then inc(j);
if h[heap[i]]<h[heap[j]] then begin
t:=heap[i];
heap[i]:=heap[j];
heap[j]:=t;
end
else break;
i:=j;
end;
end;
procedure bfs;
var i,f,head,tail:longint;
p:array[0..2*max_n]of longint;
begin
fillchar(h,sizeof(h),$3f);
head:=0;
tail:=1;
p[tail]:=t;
h[t]:=0;
while head<tail do begin
inc(head);
f:=p[head];
i:=r[f];
while i<>0 do begin
if (w[search(i)]<>0) and (h[v[i]]>h[f]+1) then begin
h[v[i]]:=h[f]+1;
inc(tail);
p[tail]:=v[i];
end;
i:=l[i];
end;
end;
end;
procedure reup(f:longint);
var i:longint;
begin
h[f]:=max_int;
i:=r[f];
while i<>0 do begin
if (w[i]<>0) and (h[v[i]]+1<h[f]) then h[f]:=h[v[i]]+1;
i:=l[i];
end;
end;
procedure push(f:longint);
var i:longint;
tt:longint;
begin
i:=r[f];
while i<>0 do begin
if (w[i]<>0) and (h[f]=h[v[i]]+1) then begin
tt:=min(flow[f],w[i]);
dec(w[i],tt);
inc(w[search(i)],tt);
dec(flow[f],tt);
inc(flow[v[i]],tt);
if (tf[v[i]]=false) and (v[i]<>s) and (v[i]<>t) then begin
tf[v[i]]:=true;
insert(v[i]);
end;
end;
i:=l[i];
if flow[f]=0 then break;
end;
end;
procedure hlpp;
var i,f,j:longint;
tt:longint;
begin
h[s]:=n;
flow[s]:=max_int;
fillchar(num,sizeof(num),0);
for i:=1 to n do
if h[i]<>max_int then inc(num[h[i]]);
i:=r[s];
while i<>0 do begin
if w[i]<>0 then begin
tt:=w[i];
dec(w[i],tt);
inc(w[search(i)],tt);
dec(flow[s],tt);
inc(flow[v[i]],tt);
if (v[i]<>s) and (v[i]<>t) and (tf[v[i]]=false) then begin
tf[v[i]]:=true;
insert(v[i]);
end;
end;
i:=l[i];
end;
while tot<>0 do begin
f:=heap[1];
del;
tf[f]:=false;
push(f);
if flow[f]<>0 then begin
dec(num[h[f]]);
if num[h[f]]=0 then
for j:=1 to n do
if (j<>s) and (j<>t) and (h[j]>h[f]) and (h[j]<=n) then h[j]:=n+1;
reup(f);
inc(num[h[f]]);
insert(f);
tf[f]:=true;
end;
end;
writeln(flow[t]);
end;
begin
read(n,m,s,t);
re;
bfs;
hlpp;
end.