[笔记]网络流基本模型

珂学分析网络流

终于不用感性分析模型了

为什么现在才补blog?因为我菜

线性规划构造最小割

求$ W = \sum_{max(x_j - x_i,0)} \times w_{ij} $的最小值。$ x_i \in \{0,1\} , w_{ij} >= 0 $。则$ i $向$ j $连$ w_{ij} $。

有$ x_i - 0 $的项则从源点连到$ i $,有$1 - x_i$的项则从$ i $连到汇点。

先选$ i $再选$ j $就$ i $到$ j $连$ inf $。

选$ i $同时选$ j $就$ i $到$ j $连$ inf $,$ j $到$ i $连$ inf $。

最大权闭合子图

给出一些权值为正和一些权值为负的点,然后点与点之间有依赖关系,如选A点就必须选择B点之类,问最后选择一些点,使得权值之和最大。

有上面基础我们也可以分析。

令$ x_i = 0$表示选,否则不选。

正权连源点,负权连汇点。

依赖连$ inf $。

最小链覆盖

(参考梁大课件(逃))

也就是从有向无环图(DAG)中选出若干点不相交的链,使得这些链覆盖所有的点,并且链的条数最小。

每个点只有一个连向它的点,和一个连出去的点。

而链的条数也就是没有连出去的点的点的数量。

(明天晚上再补吧qwq)