图论算法 ---最大流问题 长沙市雅礼中学 朱 全 民.

Slides:



Advertisements
Similar presentations
第十五章 控制方法.
Advertisements

管理运筹学 -管理科学方法 谢家平 博士 教授 博士生导师 研究领域:管理科学、运营管理、供应链管理
第四章 组合逻辑电路 第 四 章 组 合 逻 辑 电 路.
高一语文 必修1 基础知识复习专题.
第十章 依赖于机器的优化 在指令级并行的机器上,程序的运行速度依赖于下面几个因素
第四章 运筹学模型 本章重点: 线性规划基础模型、目标规划模型、运输模型 及其应用、图论模型、最小树问题、最短路问题.
第5章 回溯法 欢迎辞.
往下扎根 向上生长 ——提高学考选考教学实效的几点感想 桐庐中学 李文娟
情緒與壓力管理─背部舒緩 指導老師:彭易璟 第六組組員:會資三乙 499A0047 謝宛霖 會資三乙 499A0019 吳汶諭
第 节 地球公转及其地理意义 基础导学 地球的公转.
语 文 八年级上册 新课标(RJ).
敬业与乐业 梁启超.
人教新课标版高中必修三 6、琵琶行并序.
杜甫(公元712—公元 770),汉族,河南巩 县(今巩义市)人。字子 美,自号少陵野老,盛 唐、中唐诗人,伟大的 现实主义诗人。世称杜 拾遗、杜工部。代表作 有“三吏”“三别”。他 忧国忧民,人格高尚, 诗艺精湛,被后世尊为 “诗圣”,其诗被称为“ 诗史”。
圆明园的毁灭 丹江口市徐家沟小学 杜春晖.
作業研究 高孔廉 & 張緯良 著.
第六节 最大流问题 最大流最小割定理 基本概念 主要定理 最大流算法 算法步骤 算法复杂性 第4页缺3个证明.
语言文字应用 第二章 语音的运用及其规范.
人教版小学语文四年级下册 语文复习资料.
孔子傳第三集: 興辦私學-禮學之美 生命教育工作坊.
动态规划 中山纪念中学 宋新波 本模板来源于网络,由第一课件网整理发布,免费分享给大家使用。
圆明园的毁灭.
3.2 微分和求导法则 函数的和、差、积、商的微分与求导法则 反函数的微分与求导法则 复合函数的微分与求导法则 基本求导法则与导数公式
专题研讨课二: 数组在解决复杂问题中的作用
1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题
第四章 组合逻辑电路 4.1 概 述 4.2 组合逻辑电路的分析与设计 4.3 常用组合逻辑电路 4.4 用PLD实现组合电路
Part5语法分析 授课:胡静.
第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划
客家語拼音教學 (四縣腔) 分享者:馮美齡.
第五章 图论 5.6平面图 例 考虑把三座房和三种 设施每种都连接起来的问题, 如图7-64所示,是否有可能使 得这样的连接里不发生交叉?
递推算法 递推是一种重要的数学方法,在数学和计算机领域都有广泛应用。这种算法的特点是:一个问题的求解需要一系列的计算,在已知条件和所求问题之间总存在某种相互联系的关系。在计算时,可以找到前后过程间的数量关系,即递推。递推算法包括顺推和逆推。 递推算法的关键在于找到相邻数据项之间的关系,即递推关系,建立递推关系式。我们有时将递推算法看成一种特殊的迭代算法。
优化模型 1 存贮模型 配件厂为装配线生产若干种产品,轮换产品时因更换设 备要付生产准备费,产量大于需求时要付贮存费。该厂
第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法.
第 4 章 组合逻辑电路 4.1 组合逻辑电路的分析 4.2 组合逻辑电路的设计 4.3 常用MSI组合逻辑器件及应用
第16讲 图的矩阵表示, 赋权图与最短路径 主要内容: 1.图的矩阵表示. 2.赋权图与最短路径..
并行编译简介.
数据、模型与决策 汕头大学商学院 林佳丽.
“六一”儿童节的来历 1942年6月 ,德国法西斯枪杀了捷克利迪策村16岁以上的男性公民140余人和全部婴儿,并把妇女和90名儿童押往集中营,并焚毁了这个村庄。 为了悼念利迪策村和全世界所有在法西斯侵略战争中死难的儿童,反对帝国主义战争贩子虐杀和毒害儿童,保障儿童权利,1949年11月,国际民主妇女联合会在莫斯科召开执委会,正式决定每年6月1日为全世界少年儿童的节日,即国际儿童节。
第6章 计算机的运算方法 6.1 无符号数和有符号数 6.2 数的定点表示和浮点表示 6.3 定点运算 6.4 浮点四则运算
引例 囚徒困境: 甲、乙两个人一起携枪准备作案,被警察发现抓了起来。如果两个人都不坦白,警察会以非法携带枪支罪而将二人各判1年;如果其中一人招供而另一人不招,坦白者作为证人将不会被起诉,另一人将会被重判15年;如果两人都招供,则两人都会因罪名各判10年。这两个囚犯该怎么办? 斗鸡博弈: 两只斗鸡遇到一起,每只斗鸡都有两个行动选择:一是退下来,一是进攻。如果一方退下来,而对方没有退下来,对方获得胜利,这只公鸡则很丢面子;如果对方也退下来,则双方打个平手;如果自己没退下来,而对方退下来,自己则胜利,对方则失败
动态规划(一).
第四章 组合逻辑电路 4.1 组合逻辑电路的分析与设计 4.2 常用组合逻辑电路 4.3 组合逻辑电路的竞争与冒险.
14 毽子变乖了 开始学习.
运筹学 图与网络分析 1.
第四章 第三节 最短路径算法.
算法设计复习 内容提要: 算法设计思想回顾(递归和分治、动态规划、贪心算法、回溯法、分支限界法) 经典例子讲解 2019/4/9.
计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.
山东师范大学信息科学与工程学院软件工程研究所 徐连诚 2006年11月20日
第十四章鋁及鋁合金 改進教學計畫編號:教改進-97C-003 計畫主持人:楊慶彬.
浙江大学医学院公共技术平台 实验仪器预约管理系统系列培训 医学院公共技术平台 丁巧灵
中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月
统筹安排   成本最低.
算法导论第三次习题课
组合逻辑电路 ——中规模组合逻辑集成电路.
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
统筹安排   成本最低.
本节内容 Lua基本语法.
语文百花园八.
网络模型 Network Modeling Operations Research 运 筹 学
第3章 空间力系的简化与平衡 §3–1 空间力系的简化 §3–2 空间力系的平衡 §3–3 物体的重心 §3–4 平行力系中心.
第三章 行列式 第一节 线性方程组与行列式 第二节 排列 第三节 n阶行列式 第四节 余子式与行列式展开 第五节 克莱姆规则.
第三章 贪心方法 (Greedy Technique)
第6章 运输系统及运输优化.
第3章 运 输 问 题 3 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化
动态规划(五).
顺序查找与二分查找复习.
1.2.3 循环语句.
PASCAL语言 吉林大学计算机科学与技术学院.
1.小蝌蚪找妈妈 liǎnɡ jīnɡ 睛(眼睛)(点睛) 两(两个)(两人)(两半) (目不转睛) jiù 就(就是)(成就)(就地)
南昌大学研究生数学建模竞赛教学案例(库)
Presentation transcript:

图论算法 ---最大流问题 长沙市雅礼中学 朱 全 民

运输网络 现在想将一些物资从S运抵T,必须经过一些中转站。连接中 转站的是公路,每条公路都有最大运载量。 4 2 8 7 3 6 1 S T V1 V2 V3 V4 公路运输图

基本概念 这是一个典型的网络流模型。为了解答此题,我们先 了解网络流的有关定义和概念。 若有向图G=(V,E)满足下列条件: 有且仅有一个顶点S,它的入度为零,即d-(S) = 0,这个 顶点S便称为源点,或称为发点。 有且仅有一个顶点T,它的出度为零,即d+(T) = 0,这 个顶点T便称为汇点,或称为收点。 每一条弧都有非负数,叫做该边的容量。边(vi, vj)的容量 用cij表示。 则称之为网络流图,记为G = (V, E, C)

可行流 可行流 对于网络流图G,每一条弧(i,j)都给定一个非负数fij,这 一组数满足下列三条件时称为这网络的可行流,用f表示 它。 1. 每一条弧(i,j)有fij≤Cij 2. 流量平衡 除源点S和汇点T以外的所有的点vi,恒有: ∑j(fij)= ∑k(fjk) 该等式说明中间点vi的流量守恒,输入与输出量相等。 3. 对于源点S和汇点T有 , ∑i(fSi)= ∑j(fjT)= V(f)

可增广路 给定一个可行流f={fij}。若fij = Cij,称<vi, vj>为饱和弧;否 则称<vi, vj>为非饱和弧。若fij = 0,称<vi, vj>为零流弧;否 则称<vi, vj>为非零流弧。 定义一条道路P,起点是S、终点是T。把P上所有与P方向 一致的弧定义为正向弧,正向弧的全体记为P+;把P上所 有与P方向相悖的弧定义为反向弧,反向弧的全体记为P-。 譬如在图中,P = (S, V1, V2, V3, V4, T),那么 P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>} P- = {<V4, V3>} 给定一个可行流f,P是从S到T的一条道路,如果满足: fij是非饱和流,并且<i,j>∈ P+ , fij是非零流,并且<i,j>∈ P- 那么就称P是f的一条可增广路。之所以称作“可增广”,是因 为可改进路上弧的流量通过一定的规则修改,可以令整个 流量放大。

剩余图(残余网络) 可以沿着a--->b方向增广 剩余图G’=(V,E’) 流量网络G=(V,E)中,对于任意一条边(a,b),若 flow(a,b)<capacity(a,b) or flow(b,a)>0 则(a,b)∈ E’ 可以沿着a--->b方向增广

剩余图中,从源点到汇点的每一条路径都对应一条增广路 剩余图的权值代表能沿边增广的大小 Capacity=5 Capacity=6 Capacity=2 Flow=2 有向图 3 2 4 剩余图 剩余图中,每条边都可以沿其方向增广 剩余图中,从源点到汇点的每一条路径都对应一条增广路

割切 G = (V, E, C)是已知的网络流图,设U是V的一个子集,W = V\U,满足S ∈ U,T∈W。即U、W把V分成两个不相交 的集合,且源点和汇点分属不同的集合。 对于弧尾在U,弧头在W的弧所构成的集合称之为割切, 用(U,W)表示。把割切(U,W)中所有弧的容量 之和叫做此割切的容量,记为C(U,W),即:

割切示例 上例中,令U = {S, V1},则W = {V2, V3, V4, T},那么, C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4> =8+4+4+1=17

流量算法的基本理论 定理1:对于已知的网络流图,设任意一可行流为f, 任意一割切为(U, W),必有:V(f) ≤ C(U, W)。 定理2:可行流f是最大流的充分必要条件是:f中不 存在可改进路。 定理3:整流定理。 如果网络中所有的弧的容量是整数,则存在整数值 的最大流。 定理4:最大流最小割定理。 最大流等于最小割,即max V(f) = min C(U, W)。

最大流算法 第1步,令x=(xij)是任意整数可行流,可能是零流,给s一个永 久标号(-, ∞)。 第2步(找增广路),如果所有标号都已经被检查,转到第4步。 找到一个标号但未检查的点i, 并做如下检查, 对每一个弧(i,j),如果xij<Cij, 且j未标号,则给j一个标号(+i, δ(j) ),其中, δ(j)=min{Cij-xij , δ(i) } 对每一个弧(j, i),如果xji>0,且j未标号,则给j一个标号(-i, δ(j) ),其中, δ(j)=min{xji , δ(i) } 第3步(增广),由点t开始,使用指示标号构造一个增广路,指 示标号的正负则表示通过增加还是减少弧流量来增加还是减 少弧流量来增大流量,抹去s点以外的所有标号,转第二步继 续找增广轨。 第4步(构造最小割),这时现行流是最大的,若把所有标号的 集合记为S,所有未标号点的集合记为T,便得到最小割(S,T)。

实例

复杂度分析 设图中弧数为m,每找一条增广轨最多需要进行2m次弧 的检查。如果所有弧的容量为整数,则最多需要v(其 中v为最大流)次增广,因此总的计算量为O(mv)。

procedure maxflow; {最大流} var i, j, delta, x : integer; last : tline; {可改进路中的前趋} check : array[0 .. maxn] of boolean; {检查数组} begin repeat fillchar(last, sizeof(last), 0); fillchar(check, sizeof(check), false); last[1] := maxint; i := 0; inc(i) until (i > n) or (last[i] <> 0) and not check[i]; {找到一个已检查而未标号的点} if i > n then break; for j := 1 to n do if last[j] = 0 then if flow[i, j] < limit[i, j] then last[j] := i {正向弧} else if flow[j, i] > 0 then last[j] := -i; {反向弧} check[i] := true; until last[n] <> 0; if last[n] = 0 then break; delta := maxint; i := n; j := i; i := abs(last[j]); if last[j] > 0 then x := limit[i, j] - flow[i, j] else x := flow[j, i]; if x < delta then delta := x; until i = 1; {求改进量} inc(flow[i, j], delta) dec(flow[j, i], delta); until i = 1; {放大网络流} until false; end;

利用找增广路的其他流量算法 增广路的思想在于每次从源点搜索出一条前往汇点的 增广路,并改变路上的边权,直到无法再进行增广: 一般增广路方法:在剩余图中,每次任意找一条增广路径 增广。O(nmU) 容量缩放增广路方法:在剩余图中,每次任意找一条最大可 增广容量和的增广路径增广。O(nm*logU) 最短增广路方法(MPLA):在剩余图中,每次任意找一条含 结点数最少的增广路径增广。O(nm2) 连续最短增广路方法(DINIC):在剩余图中,每次BFS找 增广路径增广路径时,记录每个点的距离标号。在距离标 号最短路图上,不断dfs找增广路,即一次标号,多次增广。 O(n2m)

DINIC算法演示: 源点 汇点 4 2 5 3 对增广路进行增广,增广后退回到源点 1 找到增广路路线,(红色路线) 对增广路进行增广,增广后退回到源点,再无增广路线

用预流推进办法求网络流 预流推进算法给每一个顶点一个标号h(v),表示该点 到t的最短路(在残量网络中)。 第一步hights()过程,就是BFS出初始最短路,计算出每 一个顶点的h(v)。 预流推进算法的特征是运用了预流来加快运算。预流 说明图中的节点(除s, t),仅需要满足流入量 >= 流出量。 其中流入量>流出量的结点,我们称之为活动节点。 我们的算法就是不断地将活动结点,变为非活动结点, 使得预流成为可行流。

预流推进算法流程 算法过程prepare(),即首先将与s相连的边设为满流, 并将这时产生的活动结点加入队列Q。这是算法的开 始。 (1).选出Q的一个活动顶点u。并依次判断残量网络G' 中每条边(u, v),若h(u) = h(v) + 1,则顺着这里条边推 流,直到Q变成非活动结点(不存在多余流量)。 (Push推流过程) (2).如果u还是活动结点。则需要对u进行重新标号: h(u) = min{h(v) + 1},其中边(u,v)存在于G' 中。然后再 将u加入队列。(relable过程) 可以证明,通过以上算法得到的结果就是最大流。

预流推进算法示例 g(u)=12 顶点u的通过量g(u): 剩余图中,找入边权和与出边权和的较小值 增广时,每次找一个通过量最小的点v,从点v 向源点“推”大小为g(v)的流量 向汇点“拉”大小为g(v)的流量 尽量使剩余图中的边饱和 3 4 5 7 8 g(u)=12

用预流推进方法的一些网络流算法 预流推进的算法核心思想是以边为单元进行推流操作: 一般的预流推进算法:在剩余图中,维护一个预流,不断对 活跃点执行push操作,或者relable操作来重新调整这个预流, 直到不能操作。 O(nm2) 先进先出预流推进算法:在剩余图中,以先进先出队列维护 活跃点。 O(n3) 最高标号预流推进算法:在剩余图中,每次检查最高标号的 活跃点,需要用到优先队列。 O(n2m1/2)

费用流 流最重要的应用是尽可能多的分流物 资,这也就是我们已经研究过的最大 流问题。然而实际生活中,最大配置 方案肯定不止一种,一旦有了选择的 余地,费用的因素就自然参与到决策 中来。 右图是一个最简单的例子:弧上标的 两个数字第一个是容量,第二个是费 用。这里的费用是单位流量的花费, 譬如fs1=4,所需花费为3*4=12。 容易看出,此图的最大流(流量是8) 为:fs1 = f1t = 5, fs2 = f2t = 3。所以它 的费用是:3*5+4*5+7*3+2*3 = 62。 (6,3) (5,4) (3,7) (8,2) S T V1 V2 费用流问题

费用流定义 设有带费用的网络流图G = (V, E, C, W),每条弧<Vi, Vj> 对应两个非负整数Cij、Wij,表示该弧的容量和费用。 若流f满足: 流量V(f)最大。 满足a的前提下,流的费用Cost(f) =∑<i,j>∈E (fij * Wij)最小。 就称f是网络流图G的最小费用最大流。 最小费用可改进路 设P是流f的可改进路,定义∑<vi,vj>∈P+ Wij - ∑<vi,vj>∈P- Wij 为P的费用(为什么如此定义?) 如果P是关于f的可改进路中费用最小的,就称P是f的最 小费用可改进路。

费用流算法 求最小费用最大流的基本思想是贪心法。即:对于流f, 每次选择最小费用可改进路进行改进,直到不存在可 改进路为止。这样的得到的最大流必然是费用最小的。 算法可描述为: 第1步. 令f为零流。 第2步. 若无最小费用可改进路,转第5步;否则找到最小费 用可改进路,设为P。 第3步. 根据P求delta(改进量)。 第4步. 放大f。转第2步。 第5步. 算法结束。此时的f即最小费用最大流。

如何求最小费用可改进路 设带费用的网络流图G = (V, E, C, W),它的一个可行流是f。 我们构造带权有向图B = (V’, E’),其中: V’ = V。 若<Vi, Vj>∈E,fij<Cij,那么<Vi, Vj>∈E’,权为Wij。 若<Vi, Vj>∈E,fij>0,那么<Vj, Vi>∈E’,权为-Wij。 显然,B中从S到T的每一条道路都对应关于f的一条可改 进路;反之,关于f的每条可改进路也能对应B中从S到T 的一条路径。即两者存在一一映射的逻辑关系。 故若B中不存在从S到T的路径,则f必然没有可改进路;不 然,B中从S到T的最短路径即为f的最小费用可改进路。 现在的问题变成:给定带权有向图B = (V’, E’),求从S到T的 一条最短路径。

迭代法求最短路经 考虑到图中存在权值为负数的弧,不能采用Dijkstra算法;Floyd 算法的效率又不尽如人意——所以,这里采用一种折衷的算法: 迭代法(bellman算法)。 设Short[i]表示从S到i顶点的最短路径长度;从S到顶点i的最短路 径中,顶点i的前趋记为Last[i]。那么迭代算法描述如下:(为了 便于描述,令n = |V’|,S的编号为0,T的编号为n+1) step 1. 令Short[i]  +∞(1≤i≤n+1),Short[0]  0。 step 2. 遍历每一条弧<Vi, Vj>。若Short[i] + <i, j> < Short[j],则令 Short[j]  Short[i] + <i, j>,同时Last[j]  i。重复做step 2直到不 存在任何任何弧满足此条件为止。 step 3. 算法结束。若Short[n + 1]= +∞,则不存在从S到T的路径; 否则可以根据Last记录的有关信息得到最短路径。 一次迭代算法的时间复杂度为O(kn2),其中k是一个不大于n的变 量。在费用流的求解过程中,k大部分情况下都远小于n。

procedure costflow; {求最小费用最大流} var i, j, x, delta : integer; best, last : tline; {best:最短路长度;last:可改进路中的前趋顶点} more : boolean; begin repeat fillword(best, sizeof(best) shr 1, maxint); fillchar(last, sizeof(last), 0); last[1] := maxint; best[1] := 0; {赋初值} more := false; for i := 1 to n do if best[i] <> maxint then for j := 1 to n do begin if (flow[i, j] < limit[i, j]) and (best[i] + cost[i, j] < best[j]) then best[j] := best[i] + cost[i, j]; last[j] := i; more := true; end; if (flow[j, i] > 0) and (best[i] - cost[j, i] < best[j]) then best[j] := best[i] - cost[j, i]; last[j] := -i; until not more; {找最优可改进路} if best[n] = maxint then break; delta := maxint; i := n; j := i; i := abs(last[j]); if last[j] > 0 then x := limit[i, j] - flow[i, j] else x := flow[j, i]; if x < delta then delta := x; until i = 1; {求改进量} if last[j] > 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta); until i = 1; until false; {根据改进量放大流}

思维发散与探索 可改进路费用:“递增!递增?” 设f从零流到最大流共被改进了k次,每i次选择的可改 进路的费用为pi,那么会不会有p1≤p2≤p3≤……≤pk呢? 迭代法:“小心死循环!嘿嘿……” 迭代法会出现死循环吗?也就是说,构造的带权有向 图B中会存在负回路吗? 费用:“你在乎我是负数吗?” 容量:“我管的可不仅是弧。” 网络流图中的“容量”都是对弧而言的,但若是给每个 顶点也加上一个容量限制:即通过此顶点的流量的上 限;任务仍然是求从S到T的最小费用最大流。你能解 决吗?

有上下界的最大流 上面讨论的网络流都只对每条弧都限定了上界(其实 其下界可以看成0),现在给每条弧<Vi, Vj>加上一个 下界限制Aij (即必须满足Aij≤fij)。 弧上数字对第一个是上界,第二个是下界。若是撇开 下界不看,此图的最大流如图所示,流量是6;但若是 加入了下界的限制,它的最大流量就只有5了。 (3,0) (10,1) 原问题 3 (a) 2 1 (b) 增广

怎样找可行流 一种自然的想法是去掉下界,将其转化为只含上界的网络流图。 这种美好的愿望是可以实现的。具体方法如下: 设原网络流图为G = (V, E, C, A),构造不含下界的网络流图G’ = (V’, E’, C’): V’ = V∪{S’, T’} 对每个顶点x,令h-(x)= ∑<vi,vx>∈E AiX ,若h-(x)≠0,就添加一条弧 <S’, x>,其上界为h-(x) 。 对每个顶点x,令h+(x)= ∑<vx,vj>∈E AXi ,若h+(x)≠0,就添加一条弧 <x, T’>,其上界为h+(x) 。 对于任何<Vi, Vj>∈E,都有<Vi, Vj>∈E’,其上界C’ij = Cij – Aij。 新增<T, S>∈E’,其上界CTS = +∞。 在G’中以S’为源点、T’为汇点求得最大流f’。若f’中从S’发出的任意 一条弧是非饱和弧,则原网络流图没有可行流。否则可得原图的 一个可行流f = f’ + A,即所有的fij = f’ ij + Aij 。 然后再求可改进路(反向弧<Vi, Vj>必须满足fij≥Aij,而非fij≥0), 不断放大f,直到求出最大流。

另外一种构图方法 C’(u, v) = C(u, v) - B(u, v) 设 如果M(i)非负,那么设一附加源S0,则可以令C’(S0, i) = M(i)。 如果M(i)非负,那么设一附加汇T0,则可以令C’(S0, i) = -M(i)。 在这样一个加入附加源和附加汇的流网络C’中,如果 任意g(S0, i)或g(i, T0)都达到满载,那么C’中的这一个可行 流g一定对应原网络G中的一个可行流f;反之G中的任 意一个可行流f都可以对应C’中的一个g(S0, i)或g(i, T0)都 满载的流。

思考? 在一个容量有上下界的流网络G中,怎样尽快求源点s 到汇点t的一个可行的最大流?

多源点、多汇点的最大流 已知网络流图有n个源点S1、S2、……、Sn,m个汇点 T1、T2、……、Tm,求该图的最大流。这样的问题 称为多源点、多汇点最大流。 它的解决很简单: 增设一个“超级源”S’,对每个源点Si,新增弧<S’, Si>, 容量为无穷大。 增设一个“超级汇”T’,对每个汇点Ti,新增弧<Ti, T’>, 容量为无穷大。 以S’为源点、T’为汇点求最大流f。 将f中的S’和T’去掉,即为原图的最大流。

顶点有容量限制的最大流 对除源点和汇点之外的每个顶点i拆分成两个顶点 i’和i’’。新增一条弧<i’, i’’>,其容量为点i的流量限 制。 对于原图中的弧<i, j>,我们将其变换成<i’’, j’>。 对变换后的图求最大流即可。 这里我们运用到了化归的思想:将未知的“点限制” 问题转化为已知的“边限制”问题。

网络流与二部图的匹配 设二部图为G = (X, Y, E)。 增设点S’,对于所有i∈X,新增弧<S’, Xi>,容量为1; 增设点T’,对于所有i∈Y,新增一条弧<Yi, T’>,容量也 为1。原图中所有的弧予以保留,容量均为+∞。对新构 造出来的网络流图以S’为源点、T’为汇点求最大流:流 量即为最大匹配数;若弧<Xi, Yj>(i∈X,j∈Y)的流量 非零,它就是一条匹配边。 二部图最大匹配问题解决。 那么二部图的最佳匹配问题又如何? 仍然按照上述方法构图。同时令原图中弧的费用保持 不变;新增弧的费用置为0。然后以S’为源点、T’为汇 点求最小费用最大流即可。最大流的费用即为原二部 图最佳匹配的费用。

思考题1:餐巾问题 某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要 ni个软件开发人员,为了提高工作效率,公司给软件人员提供了很多的 服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这 种毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A 种方式的消毒时间需要a天时间,B中方式的消毒需要b天时间(b>a), A种消毒方式的费用为每块毛巾fA,B种消毒方式的费用为每块毛巾fB, 而买一块新毛巾的费用为f(新毛巾是已消毒的,当天可以使用);而且 f>fA>fB。公司经理正在规划在这n天中,每天买多少块新毛巾、每天送 多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然,公司 经理希望费用最低。 你的任务就是:求出提供毛巾服务的最低总费用。 输入文件:第1行为n, a, b, f, fA, fB. 第2行为n1, n2, …, nn(注:1≤f, fA, fB≤60, 1≤n≤1000) 输出文件:最少费用 input.txt output.txt 4 1 2 3 2 1 38 8 2 1 6

分析 公司第i天需要ni 块毛巾,可以把这ni 块毛巾的来源列举如下: 新买的毛巾。 第i – a – 1天之前通过A种方式消毒的毛巾。 第i – b – 1天之前通过B种方式消毒的毛巾。 我们构造带费用的网络流图G = (V, E, C)。V = {S, V1, V2, …, Vn, V1’, V2’, …, Vn’, T}, 其中S是源点、T是汇点。E中包含如下几类弧: <S, Vi>(1≤i≤n),容量为ni,费用为0。表示第i天需要ni块毛巾。 <Vi, T>(1≤i≤n),容量为正无穷大,费用为f。该弧的流量表示第i天通过方 式a得到的毛巾数量。 <Vi, Vi-a-1’>(a+2≤i≤n),容量为正无穷大,费用为fA。该弧的流量表示第i天 通过方式b得到的毛巾数量。 <Vi, Vi-b-1’>(b+2≤i≤n),容量为正无穷大,费用为fB。该弧的流量表示第i 天通过方式c得到的毛巾数量。 <Vi’, Vi-1’>(2≤i≤n),容量为正无穷大,费用为0。由于题目中没有说消毒 完的毛巾要马上使用,所以第3天就消毒好的毛巾可以暂且留着,到第7天、 第8天再使用也可以。因此这里增设此弧。 <Vi’, T>(1≤i≤n),容量为ni,费用为0。 然后对这个网络流图以S为源点、T为汇点的求最小费用最大流即可。求得的 最大流费用就是原问题的答案。

思考题2: Agent 有n名双重间谍潜伏在敌军内部,分别编号为1, 2, 3, …, n。 在给定的时间内,任意两人之间至多只进行一次点对点的双 人联系。 数据将给你一份表格,表格中将提供任意两位间谍i和j之间 进行联系的安全程度,用一个[0,1]的实数Sij表示;以及他 们联系时,能够互相传递的消息的最大数目,用一个正整数 表示Mij。(如果在表格中没有被提及,那么间谍i和j之间不 进行直接联系)。 假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安 全的,我们用[0,1]的实数ASj表示总部与间谍j之间进行联 系的安全程度,AMj则表示总部和间谍j之间进行联系时传递 的消息的最大数目。对于不和总部直接联系的间谍,他的 AMj=0(而表格中给出的他的ASj是没有意义的)。

当然,假消息从间谍手中交到敌军的情报部官员的办公桌上的过 程是绝对安全的,也就是说,间谍与敌军情报部门之间要么不进 行联系,要么其联系的安全程度是1(即完全可靠)。 现在我军司令部想利用这些间谍将k条假消息发布到敌军情报机关 的负责人。消息先由总部一次性发给n名间谍中的一些人,再通过 它们之间的情报网传播,最终由这n名间谍中某些人将情报送到敌 军手中。 对于一条消息,只有安全的通过了所有的中转过程到达敌军情报 部,这个传递消息的过程才算安全的;因此根据乘法原理,它的 安全程度P就是从总部出发,经多次传递直到到达敌军那里,每一 次传递该消息的安全程度的乘积。 而对于整个计划而言,只有当k条消息都安全的通过情报网到达敌 军手中,没有一条引起怀疑时,才算是成功的。所以计划的可靠 程度是所有消息的安全程度的乘积。 显然,计划的可靠性取决于这些消息在情报网中的传递方法。 你的任务是:拟定一个方案,确定消息应该从那些人手中传递到 那些人手中,使得最终计划的可靠性最大。

第一行:两个整数N和K,分别是间谍的总人数和计划包含的消息总数。 输入文件: 第一行:两个整数N和K,分别是间谍的总人数和计划包含的消息总数。 第二行:2n个数,前n个数实数AS1, AS2, …, ASn(范围在[0, 1]以内); 后n个数是整数AM1, AM2, …, AMn。 第三行:n个整数,其中第i(i = 1, 2, …, n)个整数如果为0表示间谍i与 敌军情报部不进行联系,如果为1则表示间谍与敌军情报部进行联系。 第四行开始,每行包括4个数,依次分别是:代表间谍编号的正整数i和 j,间谍i和j联系的安全性参数Sij([0, 1]范围内的实数),以及i、j之 间传递的最大消息数Mij(每以行的i均小于j)。 最后一行包含两个整数-1 –1,表示输入数据的结束。 0 < n < 300, 0 < k < 300。 输出文件: 输出文件中只有一行。这一行中包含一个实数P,给出的是整个计划的 可靠程度P,保留5位有效数字(四舍五入)。 如果情报根本不能将K条消息传到敌军手中,那么计划的可靠性为0。 (你可以假定,如果计划存在,那么它的可靠性大于1e-12)

输入输出样例 Agent.in Agent.out 6 13 0.00021184 6 13 0.00021184 0.9 0.7 0.8 0 0 0 2 6 8 0 0 0 0 0 0 1 0 1 1 4 0.5 2 2 3 0.9 5 2 5 0.8 2 2 6 0.8 7 3 5 0.8 2 5 6 0.8 4 -1 -1

分析 题目中的“总部”、“敌军情报部”与“间谍”的地位是完全相等的,为 了方便叙述可以将两者亦看作是间谍:“总部”编号为0、“敌军情报 部”编号为n+1。那么S0i = ASi,M0i = AMi;若间谍i可以与敌军司令 部直接联系Si,n+1=1, Mi,n+1=+∞,否则Si,n+1=0, Mi,n+1=0。 我们构造带费用的网络流图G = (V, E, M, S’)。(M为容量,S’位费用) 第i个间谍抽象成顶点i,另外增加汇点T。所有顶点构成的集合记 为V。 若Mij≠0,则存在弧<i, j>和<j, i>:其容量皆为Mij;费用Sji’ =Sij’ = ln(Sij)。 增设弧<n + 1, T>,其容量为k,费用为0。 然后以V0为源点、T为汇点求最大费用最大流。若流量小于k,则 不存在可行方案 不然则最大可靠性为:

证明 设最大费用最大流的费用为Cost,那么: 因为Cost达到最大,所以可靠性也达到最大。证毕。

思考题3:Plan问题 某软件公司有n个可选的程序项目,其中第i个项目需要耗费资金ai元,开 发成功后可获收益bi元。 当然,程序项目之间不是独立的:开发第i个项目前,必须先开发出一些 其他的项目(正如开发Office前必须开发Windows)。这些项目就称为第i 个项目的“前趋项目”。 现在给出所有项目的ai、bi,以及前趋项目。你的任务是:帮助该公司从 这n个程序项目中选择若干个进行开发,使得总收益最大。 输入文件: 输入文件有n + 3行。 第1行包含一个整数n(1≤n≤200)。 第2行有n个正整数a1, a2, …, an。 第3行有n个正整数b1, b2, …, bn。 第i + 3行(1≤i≤n)包含若干正整数:ri, k1, k2, …, kri。第一个数ri表示第i 个项目共有多少前趋项目;接下来有ri个正整数k1, k2, …, kri,分别表示 每个前趋项目的编号。 输出文件: 输出文件只有一个整数max,表示最大收益。

分析 令di = bi – ai,A = {i | di ≥ 0},B = {i | di < 0}。则di就是第i个项目的纯收益, A是所有可以获得利润的项目集合,B是所有会导致亏损的项目集合。 构造网络流图G = (V, E, C)。 V中包含两类顶点: 源点S,汇点T。 将第i个项目抽象成顶点Vi。则V1, V2, …, Vn∈V。 E中包含三类弧: 对所有的i∈A,存在弧<S, i>,容量为 di。 对所有的i∈B,存在弧<i, T>,容量为 |di|。 若第i个项目的某前趋项目编号为j,则存在弧<i, j>,容量为+∞。 然后对此网络流图求最大流,设为f。 根据f易得最小割切(U, W)(即最大流最小割定理) 那么选择的项目集合就是U,其最大收益即:

思考题4:最大获利 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公司可以有选择的建立一些中转站 (投入成本),为一些用户提供服务并获得收益(获 益之和)。那么如何选择最终建立的中转站才能让公 司的净获利最大呢?(净获利 = 获益之和 - 投入成本 之和)

【输入格式】 输入文件中第一行有两个正整数N和M 。 第二行中有N个整数描述每一个通讯中转站的建立成本,依 次为P1, P2, …, PN 。 以下M行,第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的 信息。 【输出格式】 公司可以得到的最大净获利。 【数据规模和约定】 80%的数据中:N≤200,M≤1 000。 100%的数据中:N≤5 000,M≤50 000,0≤Ci≤100,0≤Pi≤100。

分析 ①s到用户i,容量为Ci ②用户i到中转站Ai和Bi,容量为∞ ③中转站i到t,容量为Pi 考虑这个模型的割 割边不可能是②中的边,这保证了解的合法性 属于①的割边表示损失的利益 属于③的割边表示付出的代价 显然割的量越小越好,这样这道题就转换成一个最小割 的问题 根据最大流最小割定理,设sum=∑Ci,我们只要求出该 网络的最大流maxflow,则sum-maxflow就是最大获利 。

构图模型 建立一张共有n+m+2个的顶点、3*m+n条边的二分图, 求网络的最大流。 汇点 N个点 M个点 源点

思考题5:矩阵游戏 (2006年江苏省选) 题目大意: 数据范围:n,m<=1000 每个测试点最多10组数据。 对于一个n行、m列的0-1矩阵,规定在第i行中1的个数恰 为Ri个(1<=i<=n);在第j列中1的个数恰为Cj个 (1<=j<=m)。 每一行、每一列最多可以有一个格子指定为0。 问是否存在一种满足条件的0-1矩阵。 数据范围:n,m<=1000 每个测试点最多10组数据。

分析 把第i行作为点Xi,从S至Xi连一条边,容量为Ri 把第j列作为点Yj,从Yj至T连一条边,容量为Cj 若第i行第j列可以放1,那么从Xi至Yj连一条边,容 量为1 求网络最大流,判断流量值是否等于1的总数即可 边的总数达到了O(n*m) 使用MPLA可以拿到60%的分数 使用Dinic可以拿到80%的分数

深入分析 首先不考虑指定为0的格子; 因为将某2行或某2列交换,不影响问题的求解,我们不 妨将Ri与Ci从大到小排序; 将多余的1储存起来; 第三列,需要5个1, 但只有4行可以提供1;

结论 加入这个简单的判断后,MPLA算法仍然只能过 60%。 但是Dinic通过了100%的数据。 其实这题的标准方法是贪心,但使用高效的网络 流算法节省了大部分的思考时间。