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.