一种简易的方法求解流量有上下界的网络
中网络流问题
安徽 周源
研究命题
一般的，定义一个网络是一个加权的有向图G = (V , E , C )，E 中的每条弧(u , v )都有一个容量上界C (u , v )≥0。
如果人为的规定V 中的两个点s 和t ，其中s 没有入度而t 没有出度；并为E 中的每条弧(u , v )赋予一个值f (u , v )≥0，f 满足以下两个条件：
①除s , t 之外的任意一个点i 都满足：
∑∑∈∈=E
v i E i u v i f i u f ),(),(),(),(； ②任意一条E 中的弧(u , v )，都满足f (u , v )≤C (u , v )。
则称f 是G 的一个可行流，称s 为流的源且t 是流的汇。前一个条件被称为流量平衡条件，而后者则是容量限制条件。
而如果一个可行流f 使原点提供的流量
∑∈E i s i s f ),(),(达到最大，
则称f 是G 网络的最大流。
如果为G 中的每条边再加入一个容量下界：令G = (V , E , B , C )，B (u , v )表示弧(u , v )的容量下界。这样G 就是一个容量有上下界的流网络。类似的定义G 中的可行流f ：
①除s , t 之外的任意一个点i 都满足：
∑∑∈∈=E
v i E i u v i f i u f ),(),(),(),(； ②任意一条E 中的弧(u , v )，都满足B (u , v )≤f (u , v )≤C (u , v )。
同时可以定义G 中的最大流f max ，对容量有上下界的网络来说，还可以定义这个网络的最小流f min ：使原点提供流量
∑∈E i s i s f ),(min ),(达到最小的流。
在这篇文章中，我们的讨论就将围绕容量有上下界的网络展开，经过一些必要的讨论，最后将得到用于解决这一系列问题的一个较为简单的，有着较好的应用价值的算法。
正文
第一部分
为了最终能够解决问题，不妨来看一个简化版的问题：
[问题1.1]在一个有上下界的流网络G 中，不设源和汇，但要求任意一个点i 都满足流量
平衡条件：
∑∑∈∈=E
v i E i u v i f i u f ),(),(),(),( 且每条边(u , v )都满足容量限制B (u , v )≤f (u , v )≤C (u , v )的条件下，寻找一个可行流f ，或指出这样的可行流不存在。
不妨称这个问题为无源汇的可行流。
[问题1.1的解答]仔细分析一下，由于普通最大流中对每条边中流量的约束条件仅仅是f (u , v )≥0，而在这个问题中，流量却必须大于等于某一个下界。因此可以想到，设
f (u , v ) = B (u , v ) +
g (u , v ) (*)
其中g (u , v )≥0，这样就可以保证f (u , v )≥B (u , v )；同时为了满足上界限制，有
g (u , v )≤C (u , v ) - B (u , v )
令C ’(u , v ) = C (u , v ) - B (u , v )，则大致可以将g (u , v )看作无下界流网络C ’中的一个可行流。当然这样直接转化显然是不对的，因为这样仍无法体现“下界”这个条件。将(*)式代入流量平衡条件中，对于任意一个点，有：
∑∑∈∈+=+E
v i E i u v i g v i B i u g i u B ),(),()],(),([)],(),([ ∑∑∑∑∈∈∈∈-=-E v i E i u E i u E v i v i B i u B i u g v i g ),(),(),(),(),(),(),(),(
如果设：
∑∑∈∈-=E
v i E i u v i B i u B i M ),(),(),(),()( 即M (i )为流入结点i 的下界总和减去流出i 的下界总和。
如果M (i )非负，那么有：
)(]),([),(),(),(i M i u g v i g E
i u E v i +=∑∑∈∈ (1) 设一附加源S 0，则可以令
C ’(S 0, i ) = M (i )。
如果M (i )是负数，那么有：
∑∑∈∈=-E
i u E v i i u g i M v i g ),(),(),()(]),([
(2) 设一附加汇T 0，令 C ’(i , T 0) = -M (i )。
这里-M (i )是正数。
至此，附加图构造完毕。
在这样一个加入附加源和附加汇的流网络C ’中，如果任意g (S 0, i )或g (i , T 0)都达到满载，那么C ’中的这一个可行流g 一定对应原网络G 中的一个可行流f ；反之G 中的任意一个可行流f 都可以对应C ’中的一个g (S 0, i )或g (i , T 0)都满载的流。
而让从附加源点流出的弧都满载的可行流，一定是一个从附加源到附加汇的最大流。因此，求原网络G 中的一个可行流等价于求C ’中S 0至T 0的最大流，并判断从源点流出的弧是否满载：如果满载，则[问题1.1]有解，否则一定无解。
第二部分
[问题1.2]在一个容量有上下界的流网络G中，求源点s到汇点t的一个可行的最大流。
[问题1.2的解答]如果从s到t有一个流量为a的可行流f，那么从t到s连一条弧(t, s)，其流量下界B(t, s) = a，则这个图一定有一个无源汇的可行流：除了弧(t, s)的容量为a外，其余边的容量与f相同。
如果从s到t的最大流量为a max，那么从t到s连一条下界B(t, s) = a’ > a max的弧(t, s)，则从在这个改造后的图中一定没有无源汇的可行流：否则将这个可行流中的弧(t, s)除去，就得到了原图中s到t的流量为a’的流，大于最大流量a max，产生矛盾。
如果给定一个参数a，如何判断在G中从s到t是否有一个流量为a的可行流呢？综上所述，判断在G中是否有a的可行流和判断在改造后的图中是否有一个无源汇的可行流完全等价。因此，执行一次普通最大流算法，就可以完成这个任务了。
下面回到[问题1.2]中来，我们不妨二分枚举这个参数a，每次改造图后执行一次最大流来判断是否有s到t的流量为a的可行流。这样找到a能取到的最大值，也就是G图中的最大流a max了。
在一般问题中，如果所有弧上的容量为整数，那么算法一定可以在有限次计算之后停止，而算法的时间复杂度约为[log2流量]次的最大流过程，采用朴素的预流推进算法，执行一次最大流算法约需要O(N3)的时间，而[log2流量]基本可以看作与[log2N]看作同阶。因此这个算法的时间复杂度约为O(N3log2N)。
在实际应用中，这个算法是非常有价值的。但从纯理论上说，这并不是一个多项式算法，特别是当流量可能为小数的时候，算法可能会无止境的执行下去。一种解决方法是规定一个较小的误差范围，这样算法的时间复杂度为O(N3*[log2精度])：从理论上说，这也只能算一个近似算法 。另一种解决方法则是直接将答案离散为整点再进行二分，这样最多有O(2N)个整点，因此算法的时间复杂度为O(N4)。当然这种方法效率不算很高，而且实现起来很麻烦，在实际竞赛中也并不需要仅仅为追求理论上的“快感”而做出这么大的牺牲。
[问题1.3]在一个容量有上下界的流网络G中，求源点s到汇点t的一个可行的最小流。
[问题1.3的解答]与[问题1.2]类似，只是在加入弧(t, s)后二分(t, s)的容量上界C(t, s)即可。
此类问题还有一些简易的扩展，如求容量有上下界的流网络G中的最小费用最大流之类，其本质思想都是“二分参变量”，这里不再赘述。
附录
SGU中两道流量有下界试题：
p194 Reactor Cooling和p176 Flow Construction；
以及两题的程序：p194.dpr和p176.dpr。
网络流算法 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 ［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点， 对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
网络流模型总结 福州一中肖汉骏【引言】： “许多问题可以先转化为网络流问题，再运用最大流算法加以解决。而发现问题本质，根据最大流算法的特点，设计与之相配的数学模型是运用最大流算法解决问题的重要步骤。” “网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。” 注：本文大部分出自江涛老师讲稿及网络资料
图1.1 【理论部分】： 一、引入 如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。 一个实例：运输网络 参看下图，给定一个有向图G=(V ,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s 和汇点t ，现在假设在s 处有一个水源，t 处有一个蓄水池，问从s 到t 的最大水流量是多少，类似于这类的问题都可归结为网络流问题。 在流网络中，每条有向边可以被看导管。每根导管有一个固定的容量，代表物质流经这个导管的最大速率，例如一个管道每小时最多能流过200加仑液体或者一根电线最多能承载20安培的电流。流网络中的顶点可以看作是导管的连接处。除了源点和汇点之外，物质流进每个点的速率必须等于流出这个点的速率。如果我们把研究的物质特化为电流，这种“流的保持”属性就好像电路中的基尔霍夫电流定律一样。
二、网络流相关定义1 网络定义： 一个有向图 G=(V ，E)； 有两个特别的点：源点s 、汇点t ； 图中每条边(u,v)∈E ，有一个非负值的容量C(u,v) 记为 G=(V ，E ，C)，网络三要素：点、边、容量 可行流定义： 是网络G 上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件： 流的容量限制——弧： ),(),(0v u C v u P ≤≤ 对任意弧(u,v)---有向边 流的平衡限制——点： 除源点和汇点，对任意中间点有：流入u 的“流量”与流出u 的“流量”相等。即： {,}(,)(,)0x V x V u V s t P x u P u x ∈∈?∈--=∑∑有 网络的割： 一个s-t 割是这样一个边的集合，把这些边从网络中删除之后，s 到t 就不可达了。或者，正式的说，一个割把顶点集合分成A,B 两个集合，其中s 在A 中,t 在B 中，而割中的边就是所有从A 出发，到达B 的所有边。 割的容量就是割中所有边的容量的和。正式的说，就是所有从A 到B 的边的容量的和。 网络的流量： 源点的净流出“流量” 或 汇点的净流入“流量”。即： ∑∑∑∑∈∈∈∈-=-V x V x V x V x x t P t x P s x P x s P ),(),(),(),( 注意，我们这里说的流量是一种速率，而不是指总量。联系上面所说的实例，下面是一个流量为1的可行流：
给定一个有向图D=(V,A),在V中指定一点称为发点(记为),该点只有出发去的弧,指定另一点称为收点(记为),该点只有指向它的弧,其余的点叫做中间点。对于A中的每一条弧,对应一个数(简记),称之为弧的容量。通常我们把这样的D叫做网络,记为D=(V,A,C)。 (2)网络流:在弧集A上定义一个非负函数。就是通过弧 的实际流量,简记,称就是网络上的流函数,简称网络流或流,称为网络流的流量。 §4 网络最大流问题 网络最大流问题就是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要就是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4、1 基本概念与定理 1．1.网络与流 定义14 (1)网络: 例1如图7-20就是连结某产品产地与销地的交通图。弧表示从 到的运输线,弧旁的数字表示这条运输线的最大通过能力,括号内的数字表示该弧上的实际流。现要求制定一个运输方案,使从运到的产品数量最多。 可行流与最大流 在运输网络的实际问题中,我们可以瞧出,对于流有两个基本要求:
一就是每条弧上的流量必须就是非负的且不能超过该弧的最大通过能力(即该弧的容量); 二就是起点发出的流的总与(称为流量),必须等于终点接收的流的总与,且各中间点流入的流量之与必须等于从该点流出的流量之与,即流入的流量之与与流出的流量之与的差为零,也就就是说各中间点只起转运作用,它既不产出新的物资,也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=(V,A,C)与给定的流,若满足下列条件: （1）容量限制条件:对每一条弧,有 (7、9) (2)平衡条件: 对于中间点: 流出量=流入量,即对于每一个i (i≠s,t),有 (7、10) 对于出发带点,有 (7、11) 对于收点,有 (7、12) 则称为一个可行流,称为这个可行流的流量。 注意,我们这里所说的出发点就是指只有从发出去的弧,而没有指向的弧;收点就是指只有弧指向,而没有从它的发出去的弧。 可行流总就是存在的。例如令所有弧上的流,就得到一个可行流,(称为零流),其流量。 如图7-20中,每条弧上括号内的数字给出的就就是一个可行流,它显然满足定义中的条件(1)与(2)。其流量。 所谓网络最大流问题就就是求一个流,使得总流量达到最大,并且满足定义15中的条件(1)与(2),即 max
(2010-02-07 18:00:40) 转载 分类：ACM 标签： 杂谈 最大流 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance POJ 1459 Power Network POJ 2112 Optimal Milking (二分) POJ 2455 Secret Milking Machine (二分) POJ 3189 Steady Cow Assignment (枚举) POJ 1637 Sightseeing tour (混合图欧拉回路) POJ 3498 March of the Penguins (枚举汇点) POJ 1087 A Plug for UNIX POJ 1149 Pigs (构图题) ZOJ 2760 How Many Shortest Path (边不相交最短路的条数) POJ 2391 Ombrophobic Bovines (必须拆点，否则有BUG) WHU 1124 Football Coach (构图题) SGU 326 Perspective (构图题，类似于 WHU 1124) UVa 563 Crimewave UVa 820 Internet Bandwidth POJ 3281 Dining (构图题) POJ 3436 ACM Computer Factory POJ 2289 Jamie's Contact Groups (二分) SGU 438 The Glorious Karlutka River =) (按时间拆点) SGU 242 Student's Morning (输出一组解) SGU 185 Two shortest (Dijkstra 预处理，两次增广，必须用邻接阵实现，否则 MLE) HOJ 2816 Power Line POJ 2699 The Maximum Number of Strong Kings (枚举+构图)
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。
网络流经典题 一、最大流： 1、POJ 1273纯最大流 2、Poj1459 这题是标准的最大流问题，经典网络流构图，图已给出，数据规模也很适中，但是比较变态的是读数据。。。要去除空格和回车。 3、POJ_2455（相同题型：poj2112 ）二分答案+最大流 思路：二分答案，用权值比二分出来的答案小的边来建图。网络流判定的是是否能够满足找到t条路径。 4、poj1149 网络流关键在建图，图建好了，什么都解决了 5、poj3281 网络流+拆点 6、poj1637混合图欧拉回路用的是网络流 7、poj 2391 floyd + 二分搜索 + 拆点建图 +网络流 8、poj2699枚举人数+ 最大流---模型转化很重要 9、 二、最小割： 1、poj1815 求源和汇联通度的题，转换过来就是最大流最小割问题 2、POJ 2987 Firing 最小割 3、POJ 3204 最小割 实际上就是求割边，但这个割边必需是一头能被源到达，另一头能被汇到达。 4、POJ 3308 最大流最小割， 解题思路：把伞兵看成边，行列看成节点，转化为了带权二分图最小点覆盖。 三、有上下界网络流： 建议大家做poj2396和zoj2314，再看一下周源的讲义，另两题，看看题解了解一下做法，掌握思路，以后找时间再做。 资料：周源的《一种简易的方法求解流量有上下界的网络中网络流问题》， 1、POJ2396——上下界可行流 2、zoj 2314(无源汇上下界可行流) 3、【SGU 176】有下界的最小流 参考：https://www.doczj.com/doc/4b15963270.html,/2010/07/632.html 4、sgu194 无源汇上下界可行流 参考：https://www.doczj.com/doc/4b15963270.html,/ylfdrib/archive/2010/10/11/1848077.html 四、最小费用流： 1、poj3680 经典费用流问题 2、poj 3422 费用流，数据很水 3、POJ 2516简单的最小费用流问题 4、poj 2135无向图的最小费用流 5、[WC2007]剪刀石头布——费用流经典题 题目描述 在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到A胜过B，B胜过C而C又胜过A的有趣情
试卷1 一、选择题（共40分，每题2分） 1．为支持基于Internet的经济，客户的服务和业务，网络的可用性应多高（B ）A、接近100% B、接近75% C、接近50% D、接近25% 2．要组建成功的网络，需要实现哪些基本的设计目标。（E ） A、可扩展性 B、可用性 C、安全性 D、易于管理 E、以上答案都是3．在层次型网络设计中，哪一层用于连接分布层设备（B ） A、接入层 B、核心层 C、分布层 D、网络层4．设计网络时，常采用哪种策略（） A、自下而上 B、分而治之 C、自下而上 D、基于技术需求5．设计网络时，核心层包含一条或多条连接到企业边界设备的链路，这旨在支持（E ） A、Internet连接 B、VPN C、外联网 D、WAN接入 E、以上所有答案6．分布层采用哪种拓扑（C ） A、中央 B、分支 C、部分互联 D、全互联 7．对路由进行汇总有哪些好处（B ） A、增加路由器开销 B、降低路由器开销 C、增加路由选择更新 D、增大路由选择表 8．在分布层使用扩展ACL过滤数据流时，可使用哪种过滤标准：（E） A、源地址 B、目标地址 C、协议 D、端口号或应用程序E以上所有答案 9．网络的哪一层是连接终端设备的网络边缘（A ） A、接入层； B、分布层； C、核心层 D、上述答案都不对10．思科生命周期服务包含多少个阶段（C ） A、4个 B、5个 C、6个 D、7个 11．在PPDIOO的那个阶段将根据设计规范组建网络（D） A、准备阶段 B、规划阶段 C、设计阶段 D、实施阶段 12.在实施阶段，验证网络是否满足企业业务目标和设计需求被称为什么（） A、系统验证测试 B、系统级验收测试 C、安全系统测试 D、上述答案都不对 13．监视网络在特定时段的性能以创建未来评估网络时使用的参考点时，创建的是什么（A ） A、网络基准 B、网络数据路径 C、网络安全策略 D、网络运营流程
最大流问题 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。 网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 基本概念 设一个赋权有向图D=(V , A)，在V 中指定一个发点（源）vs 和一个收点（汇）vt ，且只能有一个发点vs 和一个收点vt 。（即D 中与vs 相关联的弧只能以 vs 为起点，与vt 相关联的弧只能以 vt 为终点），其他的点叫做中间点。 对于D 中的每一个弧(vi, vj)A ∈，都有一个权cij 叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =(V , A, C) 。 Vs Vt 图1 图1是一个网络。每一个弧旁边的权就是对应的容量。 网络D 上的流，是指定义在弧集合A 上的一个函数f={f(vi, vj)}={fij}，f(vi,vj)=fij 叫做弧在(vi,vj)上的流量 。 Vs Vt 图2 图2中，每条弧上都有流量fij ，例如fs1=5，fs2=3，f13=2等。 容量是最大通过能力，流量是单位时间的实际通过量。显然，0≤fij≤cij 。网络系统上流的特点： (1)发点的总流出量和收点的总流入量必相等； (2)每一个中间点的流入量与流出量的代数和等于零； (3)每一个弧上的流量不能超过它的最大通过能力（即容量）。网络上的一个流f={fij}叫做可行流，如果f 满足以下条件： （1）容量条件：对于每一个弧(vi,vj)A ∈，有0≤fij≤cij 。
（2）平衡条件： 对于发点vs ，有∑f sj ?∑f js =v (f ) 对于收点vt ，有∑f tj ?∑f jt =?v (f ) 对于中间点，有∑f ij ?∑f ji =0 其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。 网络系统中最大流问题就是，在给定的网络上寻求一个可行流f={fij}，其流量v(f)达到最大值，即从vs 到vt 的通过量最大。 最大流问题可以通过线性规划数学模型来求解。图1的最大流问题的线性规划数学模型为 max v =f s 1+f s 2 s.t. { ∑j f ij ?∑i f ij =0 i ≠s,t 0≤f ij ≤c ij 所有弧(v i ,v j ) fs1和fs2是与起点相连的两条弧上的流量。 满足上式的约束条件的解{fij}称为可行解，在最大流问题中称为可行流。 对有多个发点和多个收点的网络，可以另外虚设一个总发点和一个总收点，并将其分别 与各发点、收点连起来，就可以转换为只含一个发点和一个收点的网络。 S T 所以一般只研究具有一个发点和一个收点的网络。 我们把fij=cij 的弧叫做饱和弧，fij
从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。
2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例
浅谈网络流算法与几种流模型 吴迪1314010425 摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。 关键词：网络流Edmonds-Karp 最大流 dinic 最大流最小割网络流模型最小费用最大流 正文： 图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C），其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1 表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。 最大流理论是由福特和富尔克森于 1956 年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。 先来看一个实例。 现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下： 每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？ 这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。 若有向图G=(V,E)满足下列条件： 1、有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。 2、有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。 3、每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。 则称之为网络流图，记为G = (V, E, C) 介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。 三个基本的性质: 如果C代表每条边的容量F代表每条边的流量 一个显然的实事是F小于等于C 不然水管子就爆了 这就是网络流的第一条性质容量限制(Ca pacity Constraints):F
开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的
以下建议针对非数学系的新人，可以有计划的学习，不过别忘记，比赛是3个人的事情，所以下面涉及的知识仅靠一个人是不太可能胜任的（不排除有大牛人），这时候队友的分工协作就尤为重要了。 首先是我擅长的离散型的模型。如果你是计算机专业的，又有ACM经验的话，那么你可以大展身手了。不过对于非计算机专业的同学（比如当年的我）来说，应该是没有什么算法的经验了，所以恒心和毅力，对队友的信任，以及RP值（这点我超级自信）就非常重要了。 模型方面：姜启源的那本《数学模型》第三版，谢金星的《优化建模与LINDO/LINGO软件》就可以了，不用抱着一堆书结果什么都看不了。 算法的实现对于数学建模起着决定性的作用，一般要会以下算法。不过不用像计算机专业的那样，追求log n或者n或者nlog n的算法复杂度，只要能出结果就行，10min还是20min 都可以。不过千万不要用LINGO求解TSP啊，要好多年才出结果。 1、动态规划（工序调度，排课表，排比赛场次） 2、 0-1规划（投资，下料，运输） 3、线性规划（投资，下料，运输） 4、图的一系列问题（深度广度搜索，遍历，TSP，着色等等） 5、网络流（多半转化成规划问题） 6、最好能掌握神经网络，遗传，模拟退火，蚁群，禁忌搜索中的一种或多种，因为离散的赛题多半是组合优化的问题，大多数模型在现有算法能力下是没有精确解的（二维下料，排课表，TSP等等），所以启发式算法就显得尤为重要，比如遗传算法，MATLAB7.X已经有这个工具箱了，但是一定要弄清原理，知道怎么编码，怎么确定种群规模和遗传代数，怎么确定遗传概率和交叉概率。怎么避免早熟，怎么跳离局部最优。 软件方面： 1、 C/C++/JAVA/BASIC。随便会一种就可以，C的算法效率绝对比MATLAB高出很多，所以一般的算法还是用C实现吧。 2、 MATLAB。很无敌的数学软件，不多介绍了，最好能掌握神经网络工具箱和遗传算法工具箱的使用方法。算法的话，它可以实现的的C/C++也可以，用什么就看个人喜好了。 3、 LINGO。很无敌的规划模型的求解软件，对于离散模型来说，这个必须掌握。别忘记求解的时候在“全局最优”复选框前打钩，不然结果可能是局部最优。（LingoàOptionsàGlobal Solverà Use Global Solver）
流模型 一、流模型的思想 网络流在具体问题中的应用，最关键的部分在与模型的构造。 对于调度领域中的不同问题，可以将其转化为网络流问题进行解决。通讯网络中的数据的路径选择问题，是安排一些数据包由发点到收点的传输路径。在传输网络中，数据包经过每一条边需要一单位时间，同时一条边每次仅允许一个数据包通过。目标是极小化所有数据包传送到终点时间。若该问题中，不同种类的数据包传输路径已经提前给出，那么，其类似于调度领域中的车间作业问题为: 满足如下约束： 1.工件之间不存在优先关系，一旦一个机器开始一个工件某 阶段的加工，在此次加工过程完成之前不能加工其他 工件。 2.每次每台机器只能加工一个工件，且加工过程不允许中断。 3.每个工件各阶段的加工过程必须按照事先给定的顺序在对 应的机器上进行加工。 目标函数为极小化最大完工时间。 因为在调度问题中有诸多限制条件没有完全一致的网络流模型，所以我们需要根据不同的问题构造相应的模型。对应于此处的车间作业问题，因为工件种类的多样性，我们不仅要选择工件的类型，还要安排不同工件在同一台机器上的加工顺序。对应于通讯网络中的数据
的路径选择问题，在数据包的传输过程中不仅要选择数据包的传输路径，还需要选择数据包的类型。 建好模型之后，根据其特点我们可以不仅仅拘泥于传统的解决调度问题的方法，可以与网络流问题中的方法结合，寻找速度更快、结果更好的解决方案。 二、 流模型的应用 我们以前面提到过的车间作业问题为例。问题描述如下： 在J 台机器上安排I 种工件进行加工。第i 种工件包含i J 个阶段，每 个阶段由一个特定机器进行加工，工件i 的完工时间为：属于工件类i 的工件最后一个加工阶段i J 完成的时刻。(,)i j 代表工件i 在j 阶段的 工时，用,p i j 表示。假设工件类i 的数目为i n 。传统的车间作业问题每个工件类型仅包含一个工件，即初始工件类型向量为(1,1,...1)，是传统的NP -难问题，即使例子的规模很小也很难解。 文中首先考虑车间排序问题的松弛流控制问题，在这里我们将离散的工件用连续流进行替代，这种方法源自多级排队网络的最优控制，多级排队网络的最优控制是车间排序问题的一种随机、动态的形式。其次，通过对排序问题线性规划松弛解的舍入，可以构造解决排序问题的近似算法。这是找到解决该问题整体方案的两个重要指导思想。 应用流控制问题的最优解构造一个目标值为max C O +的可行的排序，如果适当增加初始给定的工件数量，算法的最优目标值为max (1)C O +。类似的，对于通讯网络中的数据的路径选择问题提出
【转】C#Socket网络编程入门 第一章C#Socket编程（1）基本的术语和概念 计算机程序能够相互联网，相互通讯，这使一切都成为可能，这也是当今互联网存在的基础。那么程序是如何通过网络相互通信的呢？这就是我记录这系列的笔记的原因。C#语言从一开始就是为了互联网而设计的，它为实现程序的相互通信提供了许多有用API，这类应用编程接口被称为套接字（Socket）。在开始学习C#Socket之前我们需要先来了解一下基本的术语和概念。 1.1计算机网络 计算机网络由一组通过通信信道（Communication channel）相互连接的机器组成。这些机器被称为：主机（hosts）和路由器（routers）。 *通信信道——是将字节序列从一个主机传输到另一个主机的一种手段（有线、无线（WiFi）等方式）。 *主机——是运行程序的计算机。 *路由器——是将信息从一个通信信道传递或转发到另一个通信信道。 TCP/IP网络通信流程图:
1.2分组报文 *分组报文——在网络环境中由程序创建和解释的字节序列。 1.3协议 协议相当于相互通信的一种约定，协议规定了分组报文的交换方式和它们包含意义。 互联网所使用的协议是TCP/IP协议，TCP/IP协议族主要包括: *IP协议（Internet Protocol，互联网协议） *TCP协议（Transmission Control Protocol，传输控制协议） *UDP协议（User Datagram Protocol，用户数据报协议） 1.3.1IP协议 *IP协议——是TCP/IP协议中唯一属于网络层的协议。将数据从一台主机传输到另一台主机。 *IP协议——提供了一种数据服务：每组分组报文都有网络独立处理和分发，类似于信件或包裹通过邮政系统发送一样。 *IP协议——是一个"尽力而为"（best-effort）的协议：它试图分发每一个分组报文，在网络传输过程中，偶尔也会发生丢失报文或报文顺序打乱，或者重复发送报文的情况。 在IP协议层之上是传输层（transport layer），它提供了两种可选的协议：TCP协议和UDP协议，两种协议都建立在IP层所提供的服务基础上，二者也被称为"端到端传输协议（end-to-end transport protocol）"。根据应用程序协议
网络流专题研究 福州一中肖汉骏 预备知识(参见Amber论文) 网络和流 残留网络和增广路径 最大流和最小割 主要算法 最大流 增广路方法Ford-Fulkerson method 一般增广路算法Labeling algorithm 连续增广路算法 由陈启峰提出，竞赛中相当实用，近于O(m) 容量缩放增广路算法Capacity scaling algorithm 最短增广路算法Edmonds-Karp algorithm 连续最短增广路算法Successive shortest augmenting path algorithm (Dinic augorithm) 预流推进方法Preflow-push method 一般预流推进算法Generic preflow-push algorithm 先进先出预流推进算法FIFO preflow-push algorithm 最高标号预流推进算法Highest-label preflow-push algorithm (Relabel-to-Front algorithm) 最小费用流 最小费用路方法 一般最小费用路算法(SPFA找增广路，复杂度近于O(mf)，竞赛中实用) 注意：初始流的费用必须保证是在所有同流量流中最小的。
原始-对偶算法 消圈方法 一般消圈算法 网络单纯形法 常见变形 多源多汇问题 可通过增添超级源和超级汇解决。 点有容量或费用 可以尝试拆一个点为一入点一出点，将点的限制转移到入点到出点的边上。 重边、无向边和自环的处理 对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。 而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。 而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连，得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。 给定流值的情况 可以增设一个源，向原来的源连一条容量为给定流值的边。 或者在每次增广的时候，直接将源的可改进量设为到给定流值的差。 或在回溯增广的时候，将路径的增广量同到给定流值的差比较后取小。 有上下界的流问题 注意到下界必须被满足，可以将所有必要弧抽取，经过新建的源和汇。但这时必须为原来的汇到源增添一条容量为无穷大的边，使之成为满足流量平衡条件的普通节点(注意，汇到源的流量实际上就是原网络的流值)。再运行最大流算法得到一个可行流。 另一方面，可以先满足下界，此时有一些点不满足流量平衡条件。而这可以用多源多汇问题解决。 若求的是最大流，则可以在可行流的基础上进行增广。 如果求的是最小可行流，则可以通过交换源汇，去除新增的点和边后运行最大流，将多余的流抵消。也可以通过二分汇到源的容量，运行可行流。 最大费用流 将费用取负，运行最小费用流算法。 或将SPFA的大于号反向。 可行最小费用流 从T向S连边，在这基础上找负权圈增广。
一、 引言 图论这门古老而又年轻的学科1在信息学竞赛中占据了相当大的比重。其中，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。 随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。 二、预备概念2 2.1剩余图的概念 给定一个流量网络),(111V E G =、源点s 、汇点t 、容量函数c ，以及其上的流量函数f 。我们这样定义对应的剩余图),(222V E G =：剩余图中的点集与流量网络中的点集相同，即12V V =。对于流量网络中的任一条边31),(E v u ∈，若 ),(),(v u c v u f <，那么边2),(E v u ∈，这条边在剩余图中的权值为),(),(),(v u f v u c v u g -=；同时，若0),(>v u f 那么边2),(E u v ∈，这条边在剩余图 1 图论这门学科的诞生始于18世纪欧拉证明了七桥问题，发表《依据几何位置的解题方法》一文。但图论的真正发展是从20世纪五六十年代开始的。所以说，图论是一门既古老又年轻的学科。 2 本文对一些基本的理论，如最大流最小割定理等，不做阐述，读者可以参阅相关网络流资料。 3 本文中所有涉及到的边若无指明均为有向边。
网络流基本概念 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 1.问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 图5-1 图5-2 2.网络与网络流 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。所谓网络上的流，是指
定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 3.可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： (1)容量约束：0≤f ij≤c ij，(v i,v j)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量v s(f)=汇点的净流入量（-v t(f)） 的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 4.可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： (1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤f ij 文献综述 数学与应用数学 网络最大流问题算法研究 最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题[2].最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法[6]以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界; 其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig[6]提出的网络单纯刑法和Ford和Fulkerson的增载轨算法, 他们都是伪多项式时间算法,分别由Dinic、Edmonds和Karp等提出.1973年Dinic首 次获得了时间复杂度的核心因子为nm算法.以后的几十年中,最大流算法获得了很 大的进展. 本文主要介绍的是网络最大流的几种主要算法,其中重点介绍了标号算法的详细 过程,其后给出了其在实际中的应用实例,后面介绍了现有的几种主要算法,虽然没 有给出具体的程序,但本文目的主要是了解最大流问题的解决思想,读者对网络流算 法有更深刻的认识,读者要想了解更多关于最大流问题的研究,详细可以参照Goldberg等人的研究成果, 这些程序在网上都可以轻松得到. 在这里就不再详细讲述. 下面简要介绍一下增载轨算法. 增载轨算法[5]: 沿剩余网络中从源到汇的有向路径推进流. 增载轨算法包括Ford网络最大流问题算法研究【文献综述】
相关主题
文本预览