网络流的定理与性质
增广路定理
加了反向边之后网络流可以以任意顺序增广，增广路不存在时一定为最大流。
最大流最小割定理
网络的最大流等于最小 \(S-T\) 割。
从线性规划的角度看最大流与最小割互为对偶。
增量加边
由于有增广路定理，在对网络流加边后，只要再跑一次网络流算法就能得到新的最大流。
退流删边
删边比加边困难，如果不能转化为加边，可以通过退流删边。
假如要删 \(u\rightarrow v\) 这条边，当前这条边流量为 \(k\)，则我们只需要让流入 \(u\) 的流量和流出 \(v\) 的流量减少 \(k\)，然后删除 \(u\rightarrow v\)。具体来说，从 \(u\) 到 \(S\) 跑一次最大流量为 \(k\) 的最大流，从 \(T\) 到 \(v\) 跑一次最大流量为 \(k\) 的最大流，然后将 \(u\rightarrow v\) 和其反向边的边权置为 \(0\)。