算法学习笔记(18): 网络流最小割
最小割概念
先忽略网络流，对于一个联通图的割是边的集合，删去这些边可以使原来图上的点集连通性变成两个块。
网络流的割要求两个联通块分别包含S和T（源点和汇点）。其中最小割指的是割中所有边的容量最小。
可以理解为一个联通图有很多边带权，求得一个割，称所有割中权值最小的为最小割。
最大流最小割定理
结论：对于任意网络，其最大流就等于最小割。
证明：对于任意割，任意流，都有流 ≤ 割，因为删去割会导致最大流直接归0。
当不存在增广路径时的流与割的关系：
- 如果在残差网络中不存在从 s 到 t 的路径，则说明此时的流量已经是最大流。
- 此时我们可以将节点集合 V 划分为两个部分：从 s 出发可以到达的节点集 S，以及其他节点 T=V−S。
- 边从 S 指向 T 的所有边构成一个割，并且这个割的容量即为从 S 到 T 的所有边的容量之和。
证明最大流等于最小割：
- 由于在增广路径不存在的情况下，割的容量等于当前的流量。
- 并且，由于流量在之前的步骤中是通过增广路径一步步增加的，直到无法再增加，因此此流量必然是最大流。
- 也就是说，此时的最大流等于最小割的容量。
通过最小割可以把最大流计算用于许多问题的解决
二选一关联模型
问题模型
有n个物品和两个集合A, B，如果一个物品没有放入A会花费 ai, 如果没有放入b 会花费 bi, 对于某几对物品，如果这对物品不在一个集合内，就会额外花费wi。每个物品只能在一个集合，求最小花费。
构造方法
- 建立超级源点 s 和超级汇点 t
- 对于每个物品抽象成每个点，与 s 连接权值为 ai的边， 与 t 连接权值为bi 的边
- 对于每对物品关联，对这两个点建立wi的双向边
- 最小花费就是最小割
(注：如果是多个物品，可以建立新节点建立联系)
证明&说明
对于每个物品而言，选择放入A即将和 t 的边加入割，与s就不需要加入割了。这是一个二选一的关系。
对于额外关系，如果p1，p2不在同一个集合，p1p2之间的双向边就会有一个和原来的两条边形成ST通路，需要将其加入割边。所以对于题目任意符合条件的选择，都是对应构造网络流的一个割。
将费用最小化即是最小割。
二分图最大带权独立集&最小点权覆盖集
概念
- 独立集：点集，独立集中的所有点之间都没有边
- 覆盖集：点集，所有点的边就是整个图的边
- 二分图：或称二部图，指图中的点可以分成两部分，在同一个部分的点之间没有边
问题模型
最小点权覆盖集**：**
给定一张二部图，每个点都有自己的权值，找出所有点覆盖集中权值最大的。
最大带权独立集：
给定一张二部图，每个点都有自己的权值，找出所有独立集中权值最大的独立集。
根据两者的互补关系可得：
最大带权独立集权值 = 全部点权值 - 最小点权覆盖集权值
故我们直接考虑最小点权覆盖集权值
构造方法
- 建立超级源点 s 和超级汇点 t
- 将二部图分为两部分处理，一部分连接超级源点，边权为点权
- 另一部分连接 t， 边权为点权
- 原来二部图上的所有边改为有向边，从第一部分连接到第二部分，权值为INF
证明&说明
结论：最小点权覆盖集权值就是最小割
对于一个割来说，当我们选择了二部图中的一个点时，也就是将这个点与s或t的边断开，此时，它后面连接到的边的点就没有强制性要求了，
如果我们没有选择一个点，也就是对应的边不加入割，那么为了保证不连通，这个点在二部图内连接到的后面的点都需要对应的边作为割，恰恰好对应了最小点覆盖的规律，所以点覆盖集对应的边也就必定是原图的一个割集。
则最小点权覆盖集权值就是最小割也就是最大流。
最大带权独立集权值 = 全部点权值 - 最小点权覆盖集权值 = 全部点权值 - 最大流
最大权闭合子图问题
问题模型
给定一个点权有向图，选择一个权值和最大的子图，使得子图中每个节点指向的节点也在图中。
构造方法
- 建立超级源点 s 和超级汇点 t
- 如果一个节点x的权值w是正，建立 s → x 的权值为w
- 如果节点x的权值为-w是负值，则建立一条 x → t 的边，权值为w。
- 保留原图所有边，且权值为INF。
- 用所有正权值减去最大流即可。
证明&说明
结论1：每一个符合最大权闭合子图条件的子图都对应流量网络中的一个割。
这里的子图对应到割有以下含义：
- 正权值的点被选择代表 s → x 的边不在割内
- 正权值的点不被选择代表 s → x 的边在割内
- 负权值的点被选择代表 x → t 的边在割内
- 负权值的点不被选择代表 x → t 的边不在割内
割为了保证不连通：
- 如果选择了 s → x 的边作为割，那么关于这个点的后继节点都不用它考虑了，爱选不选。相当于没有选择这个点。
- 如果没选择 s → x 的边作为割，那么为了保证不连通，需要后面所有的负权点 x → t 的边作为割。相当于选择了这个点。
结论2：我们所选择的那部分子图，权值和 = 正权值和 - (没选的正权 + 选了的负权(取正))
有趣的是，我们正权值点选择是反的，而负权值选择则是对应的，但是负权值的点对应边的权值恰好都被取负成为正数。因此现在我们不妨考虑减去值，将正权值的点也作为减去值，此时选择这个点就要减去，不选就不减去，恰好此时的闭合子图所有点代表的边的权值之和就是我们要减去的。
结论3：于是上述式子转化为：权值和 = 所有正权值之和 - 割的容量
最大权值和 = 所有正权值之和 - 最小割 = 所有正权值之和 - 最大流。
