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.