网络流总结2——最小割
内容
最小割定义
对于有向图$(V,E)$，有边权，存在源点和汇点$S,T \in V$，且$S \not = T$。
把$V$分成两个集合$\mathbf{S},\mathbf{T}$，使得$S \in \mathbf{S},T \in \mathbf{T}$，最小化
$$\sum_{u \in S,v \in T,\{u,v\} \in E} v_{\{u,v\}}$$
最小割=最大流
证明略。
最小割建模
综述
描述决策：
节点放在$S,T$？
边割不割？
做出决策->最优化线性函数。
平面图最小割
什么是平面图呢？
一个图G=(V,E)，若能将其画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入平面，或称G是可平面的。可平面图在平面上的一个嵌入称为一个平面图。如下图左边黑色的图为平面图，右边红色的图不属于平面图：
由平面图的边包围而成，其中不含图的顶点。也称为面。包围面R的所有边组成的回路称为该面的边界，回路长度称为该面的度，记为$deg(R)$。具有相同边界的面称为相邻面。由平面图的边包围且无穷大的面称为外部面。一个平面图有且只有一个外部面。如下面的平面图中，$R_0$是外部面$R_0$与$R_1, R_2, R_3$均相邻。$deg(R_0)=8,deg(R_1)=4,deg(R_2)=5$（$R_2$经过的顶点序列为$v7-v4-v6-v4-v5-v7$）, $deg(R_3)=1$：
利用欧拉公式和数学归纳法可以证明平面图G的所有面的度之和等于其边数|E|的2倍，即：
$$\sum_{i=1}^r deg(R_i) = 2|E|$$
那什么是对偶图？
设有平面图$G=(V,E)$，满足下列条件的图$G’= (V’,E’)$ 称为图G的对偶图：
$G$的任一面$R_i$内有且仅有一点$V_i’$；对$G$的域$R_i$和$R_j$的共同边界$E_k$，画一条边$E_k’=(V_i’,V_j’)$且只与$E_k$交于一点；若$E_k$完全处于$R_i$中，则$V_i’$有一自环$E_k’$，如下图$G’$是$G$的对偶图：
如果网络流中的图G可以转化为一个平面图，那么其对偶图G’中的环对应G中的割，利用最大流最小割定理转化模型，根据平面图G’与其对偶图的关系，先求出最小割。
首先连接s和t，如下图蓝色虚线，得到一个附加面，我们设附加面对应的点为s’，无界面对应的点为t’，求该图的红色的对偶图G’，最后删去s’和t’之间的边：
一条从s’到t’的路径，就对应了一个s-t割，更进一步，如果我们令每条边的长度等于它的容量，那么最小割的容量就等于最短路的长度。这样时间复杂度大大降低了。
例题
上面的是大概一年前写的，我也不知道为什么要写这么多关于平面图的东西。
海拔这题也不算是最好的例子，我觉得最好的大概就是bzoj第一道题：狼抓兔子吧
最大权闭合子图
有$n$个物品，每个物品有一个价值$V_i$（可负），你需要选出一个物品的集合，最大化其中物品的总价值，并满足$m$个限制$(x_i,y_i)$：选了$x_i$就必须选择$y_i$。
正价值物品与$S$连边，负价值物品与$T$连边，使用容量无穷的边来限制选了$x_i$就必须选择$y_i$。
用更通俗的话来理解的话，这个问题就是：现在有一个有向图，每个点有点权，点权可正可负。对于任意一条有向边$i \rightarrow j$，选择了点$i$就必须选择点$j$，你需要选择一些点使得得到权值最大。
建图方法：对于任意点$i$，如果$i$权值为正，$S$向$i$连容量为其权值的边，负权值那么$i$向$T$连容量为其权值的绝对值的边。原图所有边容量为正无穷。则最大权=正权和-最小割。
如何证明呢？首先割掉的边一定不可能是正无穷的边。而且我们发现，选择一个正权点即不割掉$S$到其的边，选择一个负权点即割掉其到$T$的边。
如何证明方案合法？其实挺显然的，对于依赖关系$i$到$j$：
假设$i$点权为正，$j$点权为负。选了$i$不选$j$即没有割掉$S$到$i$的边而且没有割掉$j$到$T$的边，显然$S$和$T$联通，不符合最小割定义。
假设$i$点权为负，$j$权为正。选了$i$不选$j$即割掉$i$到$T$的边而且割掉$S$到$j$的边，由于$S$到$T$现在不连通，我们不割这两条边同样$S$和$T$是不联通的，那么割这两边不满足割量最小，不符合最小割定义。
其余情况同理，不符合割量最小。
例题：
黑白染色和集合划分
黑白染色：
很多时候涉及到两个变量的二元函数的代价，并且有联系的变量之间的连边构成二分图，这时候可以考虑黑白染色。
比较典型的时候有集合划分模型中划分到相同集合需要付出代价的时候。
还有离散变量模型中对两个变量的和进行限制。
集合划分：
考虑如下整数规划：
$$x_i \in {0, 1}，Minimize\; P = \sum p_ix_i + \sum w_{i,j}max(x_i – x_j, 0)$$
即除了每个元素取0,1会有代价的差异之外，若两个变量取值不等则会付出额外的代价，且根据谁选择1代价可变。
根据$x_i$的取值把元素划分成两个集合，可以容易的建立出最小割模型，采用最大流求解。
集合划分模型只处理不同集合的元素对之间的代价，若要相同集合付出代价，需是二分图黑白染色后处理。
例题
离散变量模型
离散变量型网络流一般解决如下问题：
每个变量有若干个不同的取值$x_i = {0, 1, 2, \cdots, m_i}$ ，并且两个变量之间会对代价产生贡献。
一般贡献会和两个变量的差有关。
建图方式一般为，对一个点$x_i$，拆$m_i + 1$个点并连成从$S$到$T$的链，割哪一条边就代表取哪个值，贡献用两条链之间的连边表达。
例题