网络流构图总结

《网络流构图总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、网络流专题研究福州一中肖汉骏預各知识(養见Amber宛丈)网络和流残留网络和增广路径最大流和最小割最大流增广路方法Ford-Fulkersonmethod一般增广路算法Labelingalgorithm连续增广路算法由陈启峰提岀，竞赛中相当实用，近于O(m)容量缩放增广路算法Capacityscalingalgorithm最短增广路算法Edmonds-Karpalgorithm连续最短增广路算法Successiveshortestaugmentingpathalgorithm(Dinicaugorithm)预流推进方法Preflow-pushmethod一般预流推进

2、算法Genericpreflow-pushalgorithm先进先出预流推进算法FIFOpreflow-pushalgorithm最高标号预流推进算法Highest-labelpreflow-pushalgorithm(Relabel-to-Frontalgorithm)最小费用流最小费用路方法一般最小费用路算法(SPFA找增广路，复杂度近于O(mf),竞赛中实用)注意：初始流的费用必须保证是在所有同流量流中最小的。原始■对偶算法消圈方法一般消圈算法网络单纯形法多源多汇问题对通过增添超级源和超级汇解决。点有容量或费用可以尝试拆一个点为一入点一出点，将点的限制转移到入

3、点到出点的边上。重边、无向边和自环的处理对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连,得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。给定流值的情况可以增设一个源，向原来的源连一条容量为给定流值的边。

4、或者在每次增广的时候，直接将源的可改进量设为到给定流值的差。或在回溯增广的时候，将路径的增广量同到给定流值的差比较后取小。有上下界的流问题注意到下界必须被满足，可以将所有必要弧抽取，经过新建的源和汇。但这时必须为原来的汇到源增添一条容量为无穷人的边，使Z成为满足流量平衡条件的普通节点（注意，汇到源的流量实际上就是原网络的流值）。再运行最大流算法得到一个可行流。另一方面，可以先满足下界，此时有一些点不满足流量平衡条件。而这可以用多源多汇问题解决。若求的是最大流，则可以在可行流的基础上进行增广。如果求的是最小可行流，则可以通过交换源汇，去除新增的点和边后运行最大流，将多

5、余的流抵消。也可以通过二分汇到源的容量，运行可行流。最大费用流将费用取负，运行最小费用流算法。或将SPFA的大于号反向。可行最小费用流从T向S连边，在这基础上找负权圈增广。分离必要弧，使用最小费用流进行增广。单位容量网络流在构图上，可以利用只有两种収值的特殊性，容量用true和false表1和0,流量用true表1或・1,用false表0。则可以增广当且仅当xor的结果为（rue,增广可以直接变为相反的布尔常量。而单位容量网络的另一个重要性质是增广次数不超过N次。则一般增广路算法的增广次数得以改进。动态流可以对时间拆点，建立层次图处理。n个构倒的暂芳方命流表方案【例

6、1】奶牛的新年晚会《算法艺术与信息学竞赛》p315注意到奶牛和食物具备“会做”这样的关系，且其选择也只有做1盘与不做两种。而对每头奶牛有盘数限制k,对每种食物也有相应的上限值。则二分图模型呼之欲出。【例2】圆桌吃饭问题《算法艺术与信息学竞赛》p319注意到幼儿园和桌子有“派出小朋友入座”这样的关系，且其选择也只有派1个与不派两种。而对幼儿园的人数和桌子的人数都有上限值。则也可很容易想到二分图模型。【例3】赛车问题［2002］［金恺］网络流应用注意到两人的赛车均有上场次数的限制。而每次比赛均是某两辆车的对决。则就可以建立二分图模型，利用网络流解决。【例4】混合图的欧拉

7、回路《算法艺术与信息学竞赛》p324注意到边和点具有“为点增加入度”的关系，可以首先统计出每个顶点需要的入度，然后为每个点和边给出容量限制。另外一种方法是对混合图任意定向，然后统计需要反向的边的个数。反向边对于原起点来说增加了入度，对原终点来说了减少入度。如果某点的入度要增加，则可从源向它连边；如果入度需要减少，则可以向汇连边。最后只要检查所有从s出发或到达t的边是否全部满载。注意到在这种二分图上的增广实际上在对应的原图屮就是找一条路径，使得头尾顶点都被改进。这便是一种调整思想。【例5】取整矩阵YaliTrainDayl2注意到每个元素只有取下整和取上整两种选择