网络流总结(必备4篇)

网络流总结 第1篇

例如图5-9:

弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6;但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b)。

1、 V' = V∪{S', T'}

2、 对每个顶点x，令 ，若h-(x)≠0，就添加一条弧，其上界为h-(x)。

3、 对每个顶点x，令 ，若h+(x)≠0，就添加一条弧，其上界为h+(x)。

4、 对于任何∈E，都有∈E'，其上界C'ij = Cij – Aij。

5、 新增∈E'，其上界CTS = +∞。

网络流总结 第2篇

解析:定理:DAG中,最长反链 = 最小链覆盖(可以相交)

对偶定理：最长链长度 = 最小反链覆盖

.:这个定理同样适用于求解一个序列中最少的不上升子序列个数,它等于最长上升子序列的长度 (一个数向后面不比它大的数连有向边)

路径可以相交的话,等价于每一个点和它能到达的连边,这样就不用管某条边用没用过了

用floyd传递闭包(就是求连通性),然后二分图匹配按照上一个问题搞就行了

例子:BZOJ1143祭祀\(\;\;\;\;\)

网络流总结 第3篇

点覆盖：是一个点集，满足该图的所有边都有至少一个顶点在这个点集中。

定理内容：二分图最小顶点集覆盖数等于二分图最大匹配数。

选择方式

我们按遍历顺序依次标记从没有匹配的右边的点开始的所有交错路上的所有点，从左到右走匹配边，从右到左走非匹配边。取出所有被标记的左边的点和未被标记的右边的点组成的点集它就是最小点覆盖集。

为什么一定是个点覆盖集呢？

不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：

如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达，因为此时可以从右到左走该非匹配边使得左端点被标记。。

如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，所以不可能是右端点先被标记，于是它的标记只能是从这条边的左端点过来的，左端点就应该有标记。因此，它必然左端点先被标记，然后走到右端点使得它被标记；或者两个端点同时未被标记，一条匹配边恰有一个端点属于点覆盖集。

然后我们就证明出这个选择一定是一个点覆盖集。

那么我们只需要证明这是最小的点覆盖即可。

对于某个左边被标记的点是非匹配点，考虑使得它被标记的交错路，发现这是一条增广路，不满足最大匹配的定义。所以左边被标记的点是匹配点。

对于某个右边被标记的点是非匹配点，我们必然标记它，因为它可以作为交错路的开头：要么它是孤立点，交错路就为单点，要么存在至少一条从它出发的非匹配边（定义可得）。所以右边被标记的点是匹配点。

这样就和我们选出的点都是一样的了，所以这个顶点覆盖点数等于二分图最大匹配数。

那为什么是最小的呢？

如果少于最大匹配数，显然是不可能的，因为至少二分图最大匹配的每对点都不会重复，而至少两个点有一个，所以不可能小于最大匹配数。

的证。

网络流总结 第4篇

在图中选取权值和尽量大的点,使得对于途中任意一条边满足,如果他的起点被选择了,那么他的终点也应该被选择

解析: 显然是有负的点权的

首先贪心的想法,随机选一个点,看满足要求之后答案是增了还是减了,减了就不选

考虑到我们决策的变化只和一次下来选的负点权的和与正点权的和的正负性有关

于是可以把负权和正权分开考虑,构建一个二分图的模型

连边就比较容易看出来了

新建源汇,源点向正权点,负权点向汇点连上容量为权值的绝对值的边,有边的点连容量为INF的边

这样我们求解最小割,如果割了一个点的边,则表示不选该点,那么答案就为所有正点权的和减去最大流/最小割了 因为割正权点代表不选该点,价值减掉权值,割负权点代表选择了该点,价值也要减掉它的绝对值

(Updated)