JZTXT

网络流总结

发布时间 2023-04-04 21:12:33作者: mindeveloped

  1. 网络流定义
    参见 \(OI\ Wiki\)。

  2. 最大流算法
    定义：最大的可行流。
    思想：建出原图的残量网络，不断在残量网络上尝试进行增广，最后若没有可增广的路径则求得最大流。

一种可以求得最大流的算法：Dinic

  1. 求出残量网络 \(G\) 以 \(S\) 为源点的分层图 \(L\) 。
  2. 使用 DFS 算法搜索原图中的增广路径，每次从 上次经过此节点的第一条没有满流的边 \(w\in L\) （即当前弧）开始遍历。增广出的流立刻在原图上进行修改。
  3. 返回第 1 步，直到 \(S\) 到 \(T\) 不连通为止。

时间复杂度：证明参见 \(OI\ Wiki\)，本人还没有搞懂。

  1. 最小割
    性质：\(Flow_{max} = Cut_{min}\)