【模板】网络流初步

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

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 求最大流

点分裂