最大流在信息学竞赛中应用的一个模型

《最大流在信息学竞赛中应用的一个模型》由会员分享，可在线阅读，更多相关《最大流在信息学竞赛中应用的一个模型（33页珍藏版）》请在装配图网上搜索。

1、用的一个模型江涛关键字：网络 可行流 最大流 附加网络无源汇 必要弧 流的分离 有上下界的最大流 建模最大流类的模型在当今信息学比赛中有相当广泛的应 用。但在教学中，发现很多同学对流模型的原理和变形并不 掌握，只是记下经典的算法和题目，以便比赛中套用。这当然有很大的局限性，也不是学习之正道。本讲想通 过对最大流模型，特别是附加网络的一些分析、讨论，达到 抛砖引玉目的。一个实例：运输网络图 1.1 网络定义： 一个有向图G=(V, E)；有两个特别的点：源点s、汇点t；图中每条边(u,v)WE，有一个非负值的容量C(u,v) 记为 G=(V, E, C)网络三要素：点、边、容量可行流定义：是网络

2、G上的一个“流”即每条边上有个“流量”P(u,v), 要满足下面两个条件： 流的容量限制-弧：0 5 P(u,v) 5 C(u,v)对任意弧(u,v)有 向边流的平衡-点：除源点和汇点，对任意中间点有：流入 u 的“流量”与 流出 u 的“流量”相等。即：Vu e V - s,t有工 P (x, u) 一工 P (u, x) = 0xeVxeV网络的流量：源点的净流出“流量” 或 汇点的净流入“流量”。即：工 P (s, x) -工 P (x, s)=工 P (x, t) -工 P (t, x)xeVxeVxeVxeV注意，我们这里说的流量是一种速率，而不是指总量联系上面所说的实例，下面是一个

3、流量为 1 的可行流：3311032图 1.2标准图示法：图 1.3例 1.1 有一个 n*m 的国际棋盘，上面有一些格子被挖掉， 即不能放棋子，现求最多能放多少个棋子“车”，并保证它 们不互相攻击(即：不在同一行，也不在同一列)？ 分析：1) 行、列限制-最多只能一个车控制；2) 车对行、列的影响-一个车控制一个行和边； 例子：1图 1.411ts11图 1.5显然，我们要求车最多，也就是求流量最大-最大流问题下面是一个解：图 1.6即(1,3)、(2,1)、(3,2)格上各放一个车，可得到一个最优方案最大流问题寻找网络 G 上可能的最大流量（和一个有最大流量的可行 流方案），即为网络 G

4、上的最大流问题。我们再来看看图 1.1的运输网络例子，我们可能通过改进 图 1.3 得到下面这样的可行流：图 2.1求解过程中的困惑：问题 2.1流量还可能增加吗？问题 2.2如果能增加，怎样改进？最大流算法的核心-增广路径退流的概念-后向弧仔细分析图 2.1，我们发现，流量是可以增加的：图 3.1把一个流量弧（B，C）和（C，T）上的流退回到B，如图 3.2图3.1不能“直接寻找增大流的路径，是”因为当初有些弧上的流 选择不“恰当，”要“退流。”一种直观的想法就是：调整或重新搜索“当初的选择”- 难!能不能保留以前的工作，而在这之上改进呢？经过专家 们研究发现，加入退流思想-后向弧，就能再次

5、“直接寻找 增大流的路径”。增广路径（可改进路径）的定义若 P 是网络中连结源点 s 和汇点 t 的一条路，我们定义路的方向是从s到t,则路上的弧有两种：前向弧-弧的方向与路的方向一致。前向弧的全体记为P+； 后向弧-弧的方向与路的方向相反。后向弧的全体记为 P-；设 F 是一个可行流， P 是从 s 到 t 的一条路，若 P 满足 下列条件：在P+的所有前向弧(u,v)上，OWf(u,v) C(u,v); 在P-的所有后向弧(u,v)上，0f(u,v) =C(u,v);则称P是关于可行流F的一条可增广路径。图 3.3本图中:S-A-C-B-D-E-T为一增广路径。其中(C,B)为后向弧, 其

6、它为前向弧。1=11) 求路径可改进量；C (P) = min前向弧C(u,v)-f(u,v)、后向弧f(v,u) f(u ,v )eP2) 修改增广路径上的流量；四、附加网络 1-残留网络由于要考虑前向弧、后向弧，分析、描述时不简洁，在图 2.1 上直观看也不容易看出增广路径。因此我们把已经有的流量从容量中分离出来表示，引入一个与原问题等价的附加网络 1：残2022403412图 4.1其中，前向弧（黑色）上的容量为“剩余容量”=C（u,v）-f（u,v）； 后向弧（红色）上的容量为“可退流量” =f（v，u）。改造后的网如下：图 4.2在这张图上，我们找增广路径显的非常直观了!结合增广路径

7、，我们有如下定理：最大流定理如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。证明涉及最小割概念，不是本文重点，由于时间关系，从略。至此，问题 2.1和问题 2.2在这个最大流定理中同时获得解 决。求最大流的基本思想：初始化一个可行流：f (u, v) J 0 对所有u,v e V现有网络流的残留网络上有增广路径吗?*N按上面方法对增广路径改进f为最大流基于这种思想的算法，关键之处在于怎样找增广路径。常用 方法有：深度搜索dfs宽度搜索bfs优先搜索 pfs-即类似 Dijkstra 算法的标号法。另外，求最小费用最大流问题（每条边有个费用），只要把

8、 每次“找增广路径”改为“找费用最小的增广路径”即可。（证明从略）五、小结一前面几小节，回顾了最大流算法的一些基本概念和原 理，特别提到了把已有流量分离出来单独表示的方法：残留 网络。这个与原问题等价的附加网络使问题的描述、思考方 便简洁而统一。注意这几个关键词：流 分离 单独表示 等价 方便简洁它们表达了一种思路，一种分析、表示最大流问题的方法前几年的国家集训队有几篇关于最大流的论文，作者关 注的就是分析问题时怎样建立数学模型。如广东北江中学的李伟星在论文最大流的摘要中说： “许多问题可以先转化为网络流问题，再运用最大流算 法加以解决。而发现问题本质，根据最大流算法的特点，设 计与之相配的数

9、学模型是运用最大流算法解决问题的重要步骤。”福建师大附中的江鹏同学在论文从一道题目的解法试 谈网络流的构造与算法的引论中也有这样一句话：“网络流在具体问题中的应用，最具挑战性的部分是 模型的构造。这没用现成的模式可以套用，需要对各种网 络流的性质了如指掌(比如点有容量、容量有上下限、多 重边等等)，并且归纳总结一些经验，发挥我们的创造性。”是的，在信息学竞赛中很多最大流相关问题没有现成模 式可以套用，但解决最大流问题的原理和思想是相通的，前 面所说的构造等价的附加网络的思路和方法就是一种可以 借用的“现成模式”。为了进一步的讨论，先看一个更复杂的问题：例题 5.1 变形一笔画问题 在一个有向图

10、，判断能不能一笔画访问所有的边，但有 些弧上可以画多次。我们用容量C(u,v)表示弧(u,v)最多可以 重复画的次数。分析： 由于除了开始点和结束点，每个点进入次数与离开次数是相同的。因此满足流平衡条件，可以想到用流模型做。但 这里每条弧都要画到，即最少要画一次。因此，成为有上下 界的流问题。这种流的容量有上下界时求解的问题，在信息学比赛中 也很常见。下面将对这类问题做进一步讨论，我们会发现， 运用“流分离、构造等价附加网”的思想，解决的难度并不 比前面最大流问题大。六、附加网络 2-无源汇的可行流如果每个点都考虑流的平衡，而没有了源点s和汇点t, 则我们称为无源汇的可行流。有一种简单的方法可

11、以将普通的网络上的可行流要改 成无源汇的可行流：加一条边(t,s),容量为可根据需要设定为+8或其它值.1ts118例题 5.0, +81,11,图 6.1图 6.2 注：我们用弧上的 a,b 数对表示容量的上下界。无源汇的可行流问题(特指有上下界的流网络)：在一个有上下界的流网络G中，不设源和汇，但要求任 意一个点 i 都满足流量平衡条件：工 f (u, i)二 工 f (i, v)(u ,i )gE(i ,v )gE且每条边(u, v)都满足容量限制B(u, v)Wf(u, v)WC(u, v)的 条件下，寻找一个可行流f,或指出这样的可行流不存在。 不妨称这个问题为无源汇的可行流。-参见

12、周源的一种简易的方法求解流量有上下界的网络中网络流问题上图中把源、汇连接起来了，没有了源和汇，怎么求其 上的可行流呢？是的，没有了源、汇，以前的最大流算法就成了无的之 矢，一定要有源和汇。那我们为什么还要把有源、汇的问题 改成无源、汇呢？答案是破旧立新：没了旧的源、汇，我们可以更加自由地按需要设立新的 源、汇。从而使网络模型变成一个新的附加网络!七、附加网络 3-必要性流的分离对于有上下界的最大流网络流问题，我们可以看成是在 满足“必要”的下界情况时，求最大流（或最小费用等问题） 直观的一种思路就是：求一个满足下界的流fl；在fl基础上用寻找增广路径的方法，扩大流，直到没有增广路径；实现的关键

13、点在于： 问题7.1：怎样求满足下界而又不超过上界的一个流 fl？问题72：怎样增大流fl，而又同时不破坏下界？总体上看，下界是一条弧必需要满足的确定值，我们能不能把这个下界“分离”出去，从而使问题转为下界为 0， 也就是普通的最大流问题的可行流问题？先用一个类似的实例来分析说明：例题 71：N个石子，分成M堆，要求第i堆的石子数大于给定的正整数C.，问有多少种方法？i转化问题：N二N 工C个石子，要求分成M堆，问有多少i种排列方法？图 7.1图 7.2组合数学问题：一列N个1中间有N-个可分隔点，选M-1个，把1分成 M 段，有多少方法？图 7.3结果:C(N - 1,M - 1)类似地，我

14、们设法运用流分离的思想，找一个等价的附加网络 3，使问题 7.1和问题7.2得到方便而统一地解决。（一）观察一条路径情况2,6图 7.4如同例 7.1 直接把容量下界减掉怎样？41图 7.5显然，如果图 7.5 中的流想通过加上下界来对应地得到 图 7.4 中的解是不可能的。因此，这里流的分离不能用简单 减掉的方法，而应该把一个弧分离成两个弧。即加一个容量 等于下界的必要弧，使可行流分离在这两个弧上。如下图：414233图 7.6一个无源汇的可行流的方案一定是必要弧是满的。因此 现在我们先要找一个把 必要弧充满的可行流（当然也要满足 上界限制）。现在我们的目光焦点是必要弧，把他们集中起来：41

15、4图 7.7由于必要弧都是要饱和的，显然与下面图是等价的32XY图 7.8进一步，加弧(T,S)，容量不限，成无源汇可行流问题。再去除X,Y之间的连线，使Y、X分别成为新的源和汇。+ 8图 7.9如果Y到X的最大流能为2+3+3，贝I显然有:必要弧为满满足容量上界限制 保持流平衡(二)网络整体情况再来看看例 5.1，先分离必要弧：图 7.1031改造：由于可行流的源S流出与汇T流出应该是相等的, 加条边(T,S)，容量割开所有必要弧，加两个附加源Y 和汇X.图 7.11至此：问题成功转化为求Y到X的普通最大流问题。我们称这个改造后的网络模型为附加图络 3。回顾本节我们要解决的问题：问题7.1：

16、怎样求满足下界而又不超过上界的一个流fl?问题72：怎样增大流fl,而又同时不破坏下界？当求出附加网络3的最大流为 l+l+l+l+l=5 时，我们再 反过来做：把“进X”和“出Y”的对应边连上，则找到一 个有上下界容量限制和无源汇可行流。再把弧(T,S)拿走，则 问题 7.1 解决。1/31/11/11/11/11/1图 7.l2注意：原问题可行流存在无解情况，即附加网络3 的最大流 不能把源(或汇)相连的弧饱和。不同于普通最大流：因下界 为 0 时，一定有解。在得到一个可行流 fl 之后，现在我们再来看看问题 7.2。再去掉边(T,S)-上图即为弧(5,1),还原成有源汇最大流 的原问题。

17、如果要求这时的最大流,则可在这个基础上,找增广路 径来增大流,最终求得一个符合要求的最大流方案。但是要注意的是,对必要弧,我们不能退流,因此相应 的残留网络对必要弧要单独处理,或直接暂时拿走,再做附 加网络 2,如果对上例处理,则：图 7.133 4 ； 4 A图 7.14当然,本例不可能再增大流了,例子仅对解决问题 7.2 的图示说明。另外，这种情况下的增广路径改进，不会影响必要弧-即不破坏下界。源（或汇）相连的弧满了吗?1Nr无解八、小结二求容量有上下界最大流的基本思想构造附加网络3：得到新的源Y、汇X对附加网络求最大流去掉必要弧和流A恢复源、汇再次求最大流竞赛中的实用算法：周源同学在IO

18、I2004国家集训队作业一种简易的方法求 解流量有上下界的网络中网络流问题 ，是对上面方法的简 单化。简化的模型没有了上面的步骤A和B，避免了二次改造 网络，使编程容易很多。当然，代价是要多次求最大流。这个方法中用二分法，确定容量下界的最大值，求(T,S) 可能的最大流。另外，文中还提到：“在一个容量有上下界的流网络G中，求源点s到汇点 分(t, s)的容量上界C(t, s)即可。”t 的一个可行的=J小流。 类似，只是在加入弧(t, s)后二可见这个简化的方法在竞赛中用途很广。简化方法的基本思想：设定弧(T,S)容量下界为M二分增加弧 (T,S)的下界11对附加网络求最大流源(或汇)相连的弧

19、满了吗?二分减少弧 (T,S)的下界二分结束时 若有解：得到最大解 否则：无解至此，我们已经清楚地阐述了一个关于网络流方面的模型：对于“必要的流量”，用必要弧分离出来，用附加网络 3求得其上的一个可行流方案。当然，如果无解，也可 以判断出。上面两节，我们对流的 分离和流网络的等价变换做了进步发挥。与之前所用方法技巧的比较：附加网络1附加网络3退流全部可退只能部分退，下 界要保证分离流：后向弧容量：必要弧-下界 容量模型转 换直接转换有源汇T无源 汇T有源汇刘汝佳的名著算法艺术与信息学竞赛P324-P325也有这样几句话：本题和流有关，但是看起来不是去求什么最大流，而且连源和汇都没有，. 本题中处理下界的方法可以推广到任意网络。”显然，无源汇、必要弧这些概念和方法早为专家们所用 本文只是做些整理和解释工作。九、例题分析本节通过几个经典题目的模型构造，进一步体会上述的网络模型。例 9.1经典问题例 9.2 经典问题讨论题 经典问题参考文献：吴文虎 王建德，图论的算法与程序设计吴文虎 王建德，实用算法的分析与程序设计Thomas H.Cormen 等，算法导论刘汝佳 黄亮，算法艺术与信息学竞赛 朱全民，奥赛兵法周 源，论文一种简易的方法求解流量有上下界的网络中 网络流问题李伟星，论文最大流 江 鹏，论文从一道题目的解法试谈网络流的构造与算法