网络流模型总结
内容
对网络流各种姿势的总结
前言
我们可以看一下网络流24题的各种模型
可以看到，除了几道最短路还有一个恶心的IDA*/n6的DP，别的都可以转化成最大流或最小费用最大流的模型
下面就一个一个开讲吧。。
1.二分图匹配类问题
何为二分图
“二分”指中国人民银行以前发行的面值为两分的纸币和硬币
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。
简单来说就是一个图可以分成两侧，两侧的节点之间没有连边，可以形象的理解一下
何为二分图匹配
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
简单的说就是选一个边的集合，使边两边连的点不相同
①二分图最大匹配
何为二分图最大匹配
极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
最大匹配就是尽量多的选边，但要求是个匹配
二分图最大匹配问题可以用网络流和匈牙利算法解。。
网络流的话，我们可以在二分图的基础上增加源S和汇T。
1.S向U集合中每个顶点连一条容量为1的有向边。
2.V集合中每个顶点向T连一条容量为1的有向边。
3.UV集合之间的边连容量为1的有向边。
求网络最大流，流量就是匹配数，所有满流边是一组可行解。
但是这为什么是正确的呢？因为每次当选出一个匹配的时候，就相当于S到T有了一条路径满流了，也就相当于U和V中都选了一个点，而且S和T连的边都满流了，所以一个点也保证了不能被选两次。因为是最大流，所以尽量选多的边流量最大，复合了最大匹配的性质。
例题：T1
②二分图多重匹配
何为二分图多重匹配
就是匹配中一个点可以有多个匹配边相连，但是有一个上限
这个模型可以直接把上一个改一下就行了，
1.S向U集合中每个顶点连一条容量为能匹配的数量的有向边。
2.V集合中每个顶点向T连一条容量为能匹配的数量的有向边。
3.UV集合之间的边连容量为1的有向边。
*4.根据边是否满流判断可行性//不一定需要
我们可以这样理解，中间的流量为1限制了每一个匹配只能匹配两个点，到汇点和原点的连边保证了一个点可以被匹配多次。
③二分图最佳匹配
何为二分图最佳匹配
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
权值和最大的完备匹配称为最佳匹配.
这个的做法也比较好理解
1.从S向每个U连一条容量为1，费用为0的有向边。
2.从每个V向T连一条容量为1，费用为0的有向边。
3.从有连边的Ui向Vi连接一条容量为无穷大，费用为权值的有向边。
求最大费用最大流，最大费用流值就是最佳匹配。
因为每个点都要选，所以源点汇点直接连1就行了，这样流量就限制了，中间就不用管了。然后因为是最大费用最大流，所以会跑最大的权值，满足最佳匹配的性质。
例题 T18
④二分图问题引申
最小覆盖：选出最少的点，使得每一条边都至少有一个点被选中
最大独立集：选出最多的点，使得点之间两两没有边
最大匹配=最小覆盖=总点数-最大独立集
下文会讲。。
2.最大权闭合图
何为闭合图
定义一个有向图的闭合图G是该有向图的一个点集，且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。
简单的说，就是闭合图是一个点的集合，集合中任意点引出的边，那头的点也在这个集合中。也可以说，它可以是一个或多个连通块。
给每一个点一个点权，最大权闭合图是一个点权之和最大的闭合图。很好理解
下面是一个例子
这个图中，有9个闭合图（含空集）：∅，{3,4,5}，{4,5}，{5}，{2,4,5}，{2,5}，{2,3,4,5}，{1,2,4,5}，{1,2,3,4,5}
其中有最大权和的闭合图是{3,4,5}，权和为4。
那么该如何求解呢？
我们构造一个源点S，汇点T。
我们将S与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与T连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。
跑一下最大流，则最大权=正权和-最大流。
接下来就证明一下。
证明需要三个步骤【证明写得有点长和辣鸡，实在不想看就跳过吧
1.最小割为简单割
先引入一下简单割的概念
若一个 S−T 割满足割中的每条边只都与源或汇关联，称该割为简单割。
所以，我们可以看出，本网络中的最小割为简单割：
因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。
2.证明网络中的简单割与原图中闭合图存在一一对应的关系。(简单的说就是所有闭合图都是简单割，简单割也必定是一个闭合图)。
证明闭合图是简单割：如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。
证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得证。
3.证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。
首先我们记一个简单割的容量为C，且S所在集合为N，T所在集合为M。
则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解，不理解看上一个图或想象一下就明白了)。
我们记N这个闭合图的权值和为W。
则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2);
则W+C=x1+y1+x2-y2。
因为y1=y2，所以W+C=x1+x2;
x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。
所以x1+x2=所有权值为正的点的权值之和(记为TOT).
所以我们得到W+C=TOT.整理一下W=TOT-C.
到这里我们就得到了闭合图的权值与简单割的容量的关系。
因为TOT为定值，所以我们欲使W最大，即C最小，即此时这个简单割为最小割，此时闭合图为其源点S所在集合(除去S)。得证。
所以，最大权=正权和-最大流。
例题 T2
3.最小路径覆盖
何为路径覆盖
路径覆盖：在图中找一些路径，这些路径覆盖图中所有的顶点，每个顶点都只与一条路径相关联。
何为最小路径覆盖
最小路径覆盖：在所有的路径覆盖中，路径个数最小的就是最小路径覆盖了。
由上面可以得出：
1.一个单独的顶点可以是一条路径；
2．如果存在一路径p1,p2,……pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,……pk不再与其它的顶点之间存在有向边．
对于一个路径覆盖，有如下性质：
1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。
路径覆盖与二分图匹配的关系（必须是有向无环图）：
最小路径覆盖=|G|－最大匹配数
其中最大匹配数的求法是
构造二分图，把原图每个顶点i拆分成二分图U，V集合中的两个顶点Ui和Vi。对于原图中存在的每条边(i,j)，在二分图中连接边(Ui,Vj)。
然后把二分图最大匹配模型转化为网络流模型，求网络最大流。
最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。
这为什么是正确的呢
所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。
如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 – 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。
注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。
4.不相交路径
何为不相交路径
定义一个有向图G的不相交路径是该有向图的一个路径集，且该路径集的所有的每条路径没有公共点。
其实根据字面意思理解就行了。。
这种题几种类型，有比较水的，直接求最大不相交路径数，还有的有点权，要求点权最大。
如何解这种题呢
为了限制经过次数,将每个点i拆成xi,yi.
1、从yi向xi连一条容量为INF的有向边(1<i<N),
2、从S向x1连一条容量为1的有向边,
3、从yN向T连一条容量为INF的有向边,
4、如果存在边(i,j)从xi向yj连一条容量为1的有向边.
求x1到yN的最大流.为最大的路径数
正确性如何证明呢？
中间连回的边限制了一个点只能选一次，因为是最大流，所以可以直接跑就行了。。。
如何记录路径长度？
可以直接在残量网络上跑。
如何让路径长度最长？
把连回的边加上1的费用，跑最大费用。
如果限制了路径个数？
限制S连的边的流量啊
如何有多个起点或终点？
和S或T多连几条边啊。。。
有点权？
把连回的边加上费用。
路径能在点上相交？
这就更简单了，直接在原图上，起点上加S，终点加上T，终点的加边流量为INF，原图的边流量为1。有点权的话，直接落到点的出边上。
正确性？
为了保证路径没有重叠，需要在相邻的两个点上限制流量为1，由于顶层的每个点只能用1次，S向顶层点流量限制也为1。
路径能在点和边上相交？
直接把原图边的流量改成INF即可。
4.最大独立集
何为独立集
独立集：在所有的顶点中选取一些顶点，这些顶点两两之间没有连线，这些点就叫独立集
何为最大独立集
最大独立集：在所有的独立集中，顶点数最多的那个集合
要求最大独立集的话，我们要先学一下最小顶点覆盖集，因为它们是互补的
何为最小顶点覆盖集
假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
对于上面这个二分图，顶点分为左右两个集合，U集合包含1,2,3,4，V集合包含5,6,7,8,9。跑一下最大匹配
现在我们已经找到一个最大匹配M，就是上面的红线所标注的M={(1,7),(2,5),(4,8)}。
我们作如下定义：
（1）定义1、2、4、5、7、8为已经匹配过的点，其他点为未匹配的点；
（2）定义(4,8)、(1,7)、(2,5)为已匹配的边，其他边为未匹配的边。
下面我们从V集合中找出未匹配的点，就是上面标记的6和9。每次我们从右边选出一个未匹配的点，从该点出发， 做一条未匹配边->匹配边->未匹配边->……->匹配边（注意最后以匹配边结尾），并且标记用到的点，得到下图：
其中蓝色的边为我们刚才画的边，其中标记的点有2、4、5、6、8、9。 上图的两条路为：（1）9->4->8->2->5 （2）6->2->5。
这两条路都是未匹配边->匹配边->未匹配边->……->匹配边。（注意如果一个右侧未匹配点有多条边，那么这样的从该点开始的路径就有多条，上面的6和9都只有一条边，所以从每个点开始的这样的路径只有一条）。
现在我们将左侧标记的点2、4和右侧未标记的点7选出组成集合S， 那个S就是一个最小顶点覆盖集，就是S集合可以覆盖所有的边。下面证明：
（1）|S|=M，即最小顶点覆盖等于二分图最大匹配：左边标记的点全都为匹配边的顶点，因为我们构造路径的时候左边的点向右找的边都是最大匹配的边；右边未标记的点也为二分图最大匹配边的顶点。而且左边标记的加上有边未标记的正好是最大匹配的数目。
（2）S能覆盖所有的边。所有的边可以分为下面三种情况：
a、左端点标记、右端点标记；这些边一定被左侧标记的点覆盖，比如上面的2,4；
b、右端点未标记；这些边一定被右侧未标记的点覆盖，比如上面的7；
c、左端点未标记、右端点标记。
下面我们证明c这种边不会存在：若c是最大匹配中的边，由于右端点不可能是一条路径的起点（因为我们的起点都是从V集合中未匹配的点开始的），于是右端点的标记只能是在构造中从左边连过来，这是左端点必定被标记了，这时c就转化成了a；若c属于未匹配边，那么左端点必定是一个匹配点，那么c的右端点必定是一条路径的起始点，因此c的左端点也会成为一条路径的第二个点而被标记，这时c也就成了a。所以c这种边肯定是不存在的。
（3）S是最小的顶点集：因为最大匹配为M，而|S|=M，所以如果S中的点再少，那么连M个匹配的边都不能覆盖。
证明完毕。
我们可以回归正题了。如何求最大独立集？
最大独立集=所有顶点数-最小顶点覆盖
在上面这个图中最小顶点覆盖=3，即2,4,7构成最小顶点覆盖，则其他点6个构成最大独立集。且其他点不可能相连。
假设其他点相连则这条边必定没有被2,4,7 覆盖，与2,4,7是最小顶点覆盖矛盾。因此其他点之间必定没有边。而2,4,7是最小顶点覆盖，所谓最小就是不能再小了，因此我们的独立集就是最大了。非常好理解。
后记
网络流是一种简介、明了的算法，非常的实用。
正如某神说的——当你看所有题都像网络流的时候，你就学成功了。