最大流算法及其应用ppt课件.ppt

最大流算法及其应用 1 提要 网络流相关的一些概念最大流和最小割问题最大流算法的应用总结 2 一 网络流相关的一些概念 3 流网络 FlowNetwork 流网络是一个有向图G V E 其中每条边 u v E均有一非负容量c u v 0 如果 u v E 则假定c u v 0 流网络中有两个特别的顶点 源点s和汇点t 4 图1一个流网络的例子 5 流 Flow G的流是一个实值函数f f u v 表示顶点u到顶点v的流 它可以为正 为零 也可以为负 且满足下列三个性质 容量限制 对所有u v V 要求f u v c u v 反对称性 对所有u v V 要求f u v f v u 流守恒性 对所有u v V s t 要求 6 流量 整个流网络G的流量 7 割 Cut 流网络G V E 的割 S T 将划分成S和T V S两部分 使得s S t T 定义割 S T 的容量为c S T 则 8 残留网络 ResidualNetwork 给定一个流网络G V E 和流f 由f压得的G的残留网络Gf V Ef 定义cf u v 为残留网络Gf中边 u v 的容量 如果弧 u v E或弧 v u E 则 u v Ef 且cf u v c u v f u v 在下面的各种概念和方法中 我们只考虑残留网络中容量大于0的弧 但是编程时为了方便还是保留了 9 增广路径 AugmentingPath 对于残留网络Gf中的一条s t路径p称其为增广路径 定义增广路径p的残留容量为p上弧容量的最小值 后面求最大流要用到增广路径这个概念 10 增广 Augment 对于残留网络Gf中的一条增广路径p 增广的意思就是对于每一条属于p的弧 u v 将f u v 增加p的残留容量 将f v u 减少p的残留容量 这样的话 新的流f仍然满足流的三条性质 并且原流网络的流量 f 增加了 一般来说 增广过后就会修改残留网络 易得对于每一条属于p的弧 u v 要将cf u v 减去p的残留容量 cf v u 加上p的残留容量 程序实现基本都是通过直接修改残留网络来实现增广的 11 二 最大流和最小割问题 12 最大流问题 对于一个流网络G V E 其流量 f 的最大值称为最大流 最大流问题就是求一个流网络的最大流 13 增广路定理 当且仅当由当前的流f压得的残留网络Gf中不存在增广路径时 流f的流量 f 达到最大 证明在此略去 可以参见相关书籍 根据增广路定理 我们可以设计出最基本的求最大流的方法 一开始将流网络G V E 的流f置为零流 即对于 u v E时 f u v 0 然后构建残留网络 寻找增广路径增广 再修改残留网络 重复此过程 直到无法找到增广路径 此方法 之所以不是算法 是因为实现方法很多 称为Ford Fulkerson方法 14 Ford Fulkerson方法的伪代码 FORD FULKERSON METHORD G s t 1initializeflowfto02whilethereexistsanaugmentingpathp3doaugmentflowfalongp4returnf 15 最小割问题 最小割是指流网络中容量最小的割 Ford Fulkerson定理 最小割最大流定理 在流网络中 最小割的容量等于最大流的流量 证明也在此略去 根据这个定理 我们就可以通过求流网络的最大流来得到最小割 16 最大流算法 前面所讲的只是求最大流的一种方法 但怎样高效地实现还是一个问题 这个方法的最大问题就在于怎样快速地找到一条增广路径 当然我们可以用最基本的搜索 DFS或BFS 但是这种方法肯定不够高效 这时我们就需要更高效的算法 本文将重点介绍一种高效且实用的最大流算法 SAP算法 最短增广路算法 17 最短增广路算法 即每次寻找包含弧的个数最少的增广路进行增广 可以证明 此算法最多只需要进行mn 2次增广 并且引入距离标号的概念 可以在O n 的时间里找到一条最短增广路 最终的时间复杂度为O n2m 但在实践中 时间复杂度远远小于理论值 特别是加了优化之后 因此还是很实用的 此段中n表示顶点数 V m表示边数 E 18 距离标号 对于每个顶点i赋予一个非负整数值d i 来描述i到t的 距离 远近 称它为距离标号 并且满足以下两个条件 d t 0对于残留网络Gf中的一条弧 i j d i d j 1 19 允许弧和允许路 如果残留网络Gf中的一条弧 i j 满足d i d j 1 我们称 i j 是允许弧 由允许弧组成的一条s t路径是允许路 显然 允许路是残留网络Gf中的一条最短增广路 当找不到允许路的时候 我们需要修改某些点的d i 20 算法基本架构 ProcedureShortest Augmenting Path Var Begin预处理流为零流 建立残留网络计算距离函数d i 实际上一开始没有必要用BFS计算 清零就行了i s 21 whiled s ndobeginifi出发有允许弧 i j thenbegin记录j在允许路上的前驱结点ii j ifi tthenbegin沿着增广路增广 修改残留网络i s end end 22 elseifi出发有弧thend i min d j 1 i j 在残留网络中 elsebegind i n 禁止以后再考虑顶点i当i s时退回到前一步end end End 23 SAP的优化 SAP算法有两个重要的优化 Gap优化和当前弧优化 24 Gap优化 我们可以注意到由于残留网络的修改只会使d i 越来越大 因为修改前d i d j 1 而修改后会存在d i d j 1 因此变大了 所以说d i 是单调递增的 这就提示我们 如果d函数出现了 断层 即没有d i k 而有d i 1 这时候必定无法再找到增广路径 我们可以这么想 现在的i满足d i k 1 发现没有一个d j 为k 因此就会尝试去调整d i 但是d i 是单调递增的 只会越来越大 所以k这个空缺便永远不会被补上 也就是说无法再找到增广路径 25 当前弧优化 可以注意到一个事实 如果说在某次迭代中从i出发的弧 i j 不是允许弧 则在顶点i的标号修改之前 i j 都不可能是允许弧 因为d i 不变 d j 不减且d i d j 1 这样 在查找允许弧的时候只需要从上一次找到的允许弧开始找 所以我们增加 当前弧 这个数据结构 记录当前顶点找到的允许弧 只有在修改这个顶点标号时才会更改这个顶点的当前弧 26 SAP的两个优化效果比较 程序1 SAP程序2 SAP Gap程序3 SAP 当前弧程序4 SAP Gap 当前弧 测试题目 NOI2006 最大获利 27 比较结果 表中时间单位 s 测试环境 Core2DuoE4600 2 4GHz 2GB 论效果的话 可能Gap优化占了上风 但是想要获得最佳效果 还是要把两种优化结合起来使用的 28 三 最大流算法的应用 29 最大流模型 一个典型的最大流模型就是二分图的最大二分匹配 二分图G X Y E 其中X和Y是两个不相交的点集 并且对于每对 u v E u X且v Y 二分图的最大二分匹配问题就是从E中选择一些边 使得每个点最多在选择的边里出现一次 问最多能选多少条边 30 图2一个二分图的例子及其最大匹配 实线表示选中的边 虚线表示未选中的边 31 分析 实际上我们可以将二分图的最大匹配问题转换为最大流问题 增加源和汇 将源连到每个左边的点 将每个右边的点连到汇 并把原来的边改为有向的 从左边的点指向右边的点 最后把图中所有弧的容量赋为1 这个流网络的最大流即为原二分图的最大匹配 32 图3新建的流网络 图中弧的容量均为1 33 分析 续 对于每个左边的点 进去的流量最多只有1 对于每个右边的点 出去的流量最多只有1 所以每个点最多在选中的边里最多出现一次 选中的边即为中间流量为1的弧 又因为流最大 所以结果就是原二分图的最大二分匹配 关于二分图的最大二分匹配还有另外一种算法 匈牙利算法 具体的内容可以参阅其他资料 34 最小割模型 最小割问题是网络流建模里的一个难点 由于最小割模型在原问题中往往很隐蔽 有时确实需要凭感觉 看一道比较有难度的例题 最大获利 NOI2006第二试 35 最大获利 问题描述 新的技术正冲击着手机通讯市场 对于各大运营商来说 这既是机遇 更是挑战 THU集团旗下的CS T通讯公司在新一代通讯技术血战的前夜 需要做太多的准备工作 仅就站址选择一项 就需要完成前期市场研究 站址勘测 最优化等项目 在前期市场调查和站址勘测之后 公司得到了一共N个可以作为通讯信号中转站的地址 而由于这些地址的地理位置差异 在不同的地方建造通讯中转站需要投入的成本也是不一样的 所幸在前期调查之后这些都是已知数据 建立第i个通讯中转站需要的成本为Pi 1 i N 另外公司调查得出了所有期望中的用户群 一共M个 关于第i个用户群的信息概括为Ai Bi和Ci 这些用户会使用中转站Ai和中转站Bi进行通讯 公司可以获益Ci 1 i M 1 Ai Bi N THU集团的CS T公司可以有选择的建立一些中转站 投入成本 为一些用户提供服务并获得收益 获益之和 那么如何选择最终建立的中转站才能让公司的净获利最大呢 净获利 获益之和 投入成本之和 36 输入格式 输入文件中第一行有两个正整数N和M 第二行中有N个整数描述每一个通讯中转站的建立成本 依次为P1 P2 PN 以下M行 第 i 2 行的三个数Ai Bi和Ci描述第i个用户群的信息 所有变量的含义可以参见题目描述 输出格式 你的程序只要向输出文件输出一个整数 表示公司可以得到的最大净获利 37 输入样例 5512345123234133142453 输出样例 4 38 样例说明 选择建立1 2 3号中转站 则需要投入成本6 获利为10 因此得到最大收益4 评分方法 本题没有部分分 你的程序的输出只有和我们的答案完全一致才能获得满分 否则不得分 数据规模和约定 80 的数据中 N 200 M 1000 100 的数据中 N 5000 M 50000 0 Ci 100 0 Pi 100 39 分析 看到了 最大 这个字眼 很多人便以为此题与最小割没有关系 但实际上不是 由于 净获利 获益之和 投入成本之和 所有用户群的获益 损失用户群的获益 建设中转站的代价 要使净获利最大 即使 损失用户群的获益 建设中转站的代价 最小 这就将 最大 变成了 最小 40 建模 下面建立流网络 以每一个中转站和用户群为顶点 并增加源和汇 连接源到每个中转站 容量为建设该中转站的代价 连接每个用户群到汇 容量为该用户群的收益 对于每个用户群 连接它的两个相关中转站到这个用户群 容量为 由于割将所有的点分为S和T两个集合 又因为是最小割 所以割的容量必定不会包含中间那些容量为 的弧 因此每个用户群及其两个相关的中转站必定在一个集合中 那么T中包含的中转站便是我们选择建设的 S中包含的用户群即为放弃的用户群 割的容量为源到所有T中包含的中转站的建设费用和加上S中包含的所有用户的获益和 又因为割的容量最小 所以结果最优 41 图4样例建成的流网络 中间弧的容