Logic
向着梦想进发
Logic's Blog

【模板】网络流初步

初学网络流,概念有点多
现在来梳理一下

yxc代码

源点,汇点

s表示源点,t表示汇点

流网络

  • 流网络是一张有向图,对于 $ G = (V, E) $, 有属性 $ c(u, v) $
  • 容量类比于水管在单位时间内流过的最大水量

可行流 $ f $

  • 容量限制:
    $$
    0 \le f(u, v) \le c(u, v)
    $$

  • 流量守恒:
    $$
    \forall x \in {V \cup \left\{ s, t \right\} }, st.
    \sum _{(v, x) \in E} {f(v, x) = \sum _ {(x, v) \in E}} f(x, v)
    $$

  • 斜对称
    $$
    f(u, v) = -f(v, u)
    $$

注意:只有在残留网络中才有斜对称

  • 流函数
    $$
    \lvert f \rvert = \sum _{(s, v) \in E} f(s,v) - \sum _{(v, s) \in E} f(v, s)
    $$

$$
流出源点的水流-流入源点的水流
$$

  • $ f + f' $ 也是 $ G $ 的一个可行流,其中 $ f' $表示在残留网络中的可行流

  • $ \lvert f + f' \rvert = \lvert f \rvert + \lvert f' \rvert $

  • 若 $ \lvert f' \rvert = 0 $ 即没有增广路时,则 $ f $ 为最大流

最大流

$ \lvert f \rvert $ 最大的可行流

残留网络

对原图 $ G $ 中的一个可行流而言,记为
$$
G _ f = (V _ f, E _ f)
$$

其中

$$
V _f = V, E _f = E 和 E中所有的反向边
$$

残留网络的容量为
$$ c'(u, v) =
\begin{cases}
c(u, v) - f(u, v), {(u, v) \in E} \\
f(v, u), {(v, u) \in E}
\end{cases} $$

  • $ V $ 将 $ G = (V, E) $ 不重不漏地分为两个子集 $ S,T $ ,其中 $ S \cup T = G, S \cap T = \varnothing, s \in S, t \in T $

  • 容量
    即从$S$指向$T$的边的容量和
    $$
    c(S, T) = \sum _{u \in S} {\sum _ {v \in T} c(u, v)}
    $$

  • 流量
    $$
    f(S, T) = \sum _ {u \in S} {\sum _ {v \in T} f(u, v)} - \sum _ {u \in T} {\sum _ {v \in S} f(u, v)}
    $$

  • 最小割
    容量最小的割

性质:

  1. $ \forall {[S, T]}, \ f(S, T) \le c(S, T) $
  2. $ f(S, T) = \lvert f \rvert $

集合 $X$, $Y$ 的流量

即:
$$
f(X, Y) = \sum _ {u \in X} {\sum _ {v \in Y} f(u, v)} - \sum _ {u \in X} {\sum _ {v \in Y} f(u, v)}
$$

有性质:

  1. $ f(X, Y) = -f(X, Y) $
  2. $ f(X, X) = 0 $
  3. $ f(Z, X \cup Y) = f(Z, X) + f(Z, Y),其中 X \cap Y = \varnothing $
  4. $ f(X \cup Y, Z) = f(X, Z) + f(Y, Z) $

最大流最小割定理

  1. 可行流 $ f $ 是最大流
  2. $ G _ f $ 中不存在增广路
  3. $ \exists {[S, T]}, st. \lvert f \rvert = c(S, T) $

以上命题等价

EK求最大流

dinic 求最大流

点分裂

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/%e7%bd%91%e7%bb%9c%e6%b5%81%e5%88%9d%e6%ad%a5/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可

发表回复

textsms
account_circle
email

Logic's Blog

【模板】网络流初步
初学网络流,概念有点多 现在来梳理一下 yxc代码 源点,汇点 s表示源点,t表示汇点 流网络 流网络是一张有向图,对于 $ G = (V, E) $, 有属性 $ c(u, v) $ 容量类比于水管在单位时间内…
扫描二维码继续阅读
2021-12-03