前言

Class taken on 4.2

Written on 4.29

Flow

解决问题类

网络流是用有向图每条边来模拟流动，有流量限制的情况下，求解最大流量（有时以及最小费用）的问题。

同时也是将各类问题（尤其匹配问题）通过建模为网络流来用网络流算法求解的一个方法。

解决问题的一般特点：

• 数据范围不大不小，\(n\) 在 \(10^3\) 到 \(10^4\) 量级。

• 偏向匹配相关（如一个位置匹配一个人，一条边匹配一条路径之类的）的问题。

• 偏向分配相关（如把一些人分成两组满足什么关系有代价，问最小代价）一类

常见最大流，最小割，最小费用最大流问题。

概念

网络（network）是指一个特殊的有向图 \(G=(V,E)\)，其与一般有向图的不同之处在于有容量和源汇点。

\(E\) 中的每条边 \((u, v)\) 都有一个被称为容量（capacity）的权值，记作 \(c(u, v)\)。当 \((u,v)\notin E\) 时，可以假定 \(c(u,v)=0\)。

\(V\) 中有两个特殊的点：源点（source）\(s\) 和汇点（sink）\(t\)（s \neq t）。

对于网络 \(G=(V, E)\)，流（flow）是一个从边集 \(E\) 到整数集或实数集的函数，其满足以下性质。

容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 \(0 \leq f(u,v) \leq c(u,v)\)；
流守恒性：除源汇点外，任意结点 \(u\) 的净流量为 0。其中，我们定义 \(u\) 的净流量为 \(f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u)\)。
对于网络 \(G = (V, E)\) 和其上的流 \(f\)，我们定义 \(f\) 的流量 \(|f|\) 为 s 的净流量 \(f(s)\)。作为流守恒性的推论，这也等于 \(t\) 的净流量的相反数 \(-f(t)\)。

对于网络 G = (V, E)，如果 {S, T} 是 V 的划分（即 S \cup T = V 且 S \cap T = \varnothing），且满足 s \in S, t \in T，则我们称 {S, T} 是 G 的一个 s-t 割（cut）。我们定义 s-t 割 {S, T} 的容量为 ||S, T|| = \sum_{u \in S} \sum_{v \in T} c(u, v)。

问题 1：最大流问题

给定图，求解这张图的合法流中流量最大的。

经典建模：二分图最大匹配。

建立超级源点向左侧全连流量为 \(1\) 的边，超级汇点向右侧全连流量为 \(1\) 的边（超级源点和超级汇点也是网络流题目必备套路，所有题都要用），表示每个点只参与一次匹配。

将图中出现的其他边每条流量设置为 \(1\) 表示每条边可以且仅可以参加一次匹配。

跑最大流就是最大匹配数。