网络流算法的应用

Ⅰ 家园 网络流拆点 pascal

】动态规划 阶段

动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。
文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。
文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。

动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。
要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态规划的本质。
§1动态规划的本质
动态规划是在本世纪50年代初，为了解决一类多阶段决策问题而诞生的。那么，什么样的问题被称作多阶段决策问题呢？
§1.1多阶段决策问题
说到多阶段决策问题，人们很容易举出下面这个例子。
[例1] 多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。
仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边就被分成了三类（AàB、BàC、CàD）。我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。
从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如下：
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列[1]。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。
从上述的定义中，我们可以明显地看出，这类问题有两个要素。一个是阶段，一个是决策。
§1.2阶段与状态
阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。常用字母k表示阶段变量。[1]
阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子，就有A、B、C、D这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题（我的感觉，特别是信息学问题）中，阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。
阶段之间是怎样相互联系的？就是通过状态和状态转移。
状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。[1]
状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。在上面的例子中，行人从出发点A1走过两个阶段之后，可能出现的情况有三种，即处于C1、C2或C3点。那么第三个阶段就有三个状态S3=。
每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移（暂不定义）。上例中C3点可以从B1点过来，也可以从B2点过来，从阶段2的B1或B2状态走到阶段3的C3状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。
说到这里，可以提出应用动态规划的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展，而只能通过当前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结[1]”。这就是无后效性。对这个性质，下文还将会有解释。
§1.3决策和策略
上面的阶段与状态只是多阶段决策问题的一个方面的要素，下面是另一个方面的要素——决策。
决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk) ÎDk(sk)。[1]
决策是问题的解的属性。决策的目的就是“确定下一阶段的状态”，还是回到上例，从阶段2的B1状态出发有三条路，也就是三个决策，分别导向阶段3的C1、C2、C3三个状态，即D2(B1)=。
有了决策，我们可以定义状态转移：动态规划中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态sk和本阶段的决策uk确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk,uk)称为状态转移方程。
这样看来，似乎决策和状态转移有着某种联系。我的理解，状态转移是决策的目的，决策是状态转移的途径。
各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n=表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最有效果的策略就是最优策略。[1]
说到这里，又可以提出运用动态规划的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略[1]。这就是最优化原理。简言之，就是“最优策略的子策略也是最优策略”。
§1.4最优化原理与无后效性
这里，我把最优化原理定位在“运用动态规划的前提”。这是因为，是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略p1,n同任何一个阶段k上的决策uk或任何一组阶段k1…k2上的子策略pk1,k2都不存在任何关系。如果要对这样的问题动态规划的话，我们从一开始所作的划分阶段等努力都将是徒劳的。
而我把无后效性定位在“应用动态规划的条件”，是因为动态规划是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段，重新选定状态，或者增加状态变量的个数等手段，来是问题满足无后效性这个条件。说到底，还是要确定一个“序”。
在信息学的多阶段决策问题中，绝大部分都是能够满足最优化原理的，但它们往往会在后效性这一点上来设置障碍。所以在解题过程中，我们会特别关心“序”。对于有序的问题，就会考虑到动态规划；对于无序的问题，也会想方设法来使其有序。
§1.5最优指标函数和规划方程
最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为fk(sk)，它表示从第k段状态sk采用最优策略p*k,n到过程终止时的最佳效益值[1]。
最优指标函数其实就是我们真正关心的问题的解。在上面的例子中，f2(B1)就表示从B1点到终点D1点的最短路径长度。我们求解的最终目标就是f1(A1)。
最优指标函数的求法一般是一个从目标状态出发的递推公式，称为规划方程：

其中sk是第k段的某个状态，uk是从sk出发的允许决策集合Dk(sk)中的一个决策，Tk(sk,uk)是由sk和uk所导出的第k+1段的某个状态sk+1，g(x,uk)是定义在数值x和决策uk上的一个函数，而函数opt表示最优化，根据具体问题分别表为max或min。
，称为边界条件。
上例中的规划方程就是：

边界条件为
这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。在我们的信息学问题中，也有很多有着确定的初始状态。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。
我们本节所讨论的这些理论虽然不是本文的主旨，但是却对下面要说的动态规划的特点起着基础性的作用。
§2动态规划的设计与实现
上面我们讨论了动态规划的一些理论，本节我们将通过几个例子中，动态规划的设计与实现，来了解动态规划的一些特点。
§2.1动态规划的多样性
[例2] 花店橱窗布置问题（IOI99）试题见附录
本题虽然是本届IOI中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？
<方法1>以花束的数目来划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量sk表示第k束花所在的花瓶。而对于每一个状态sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数fk(sk)表示前k束花，其中第k束插在第sk个花瓶中，所能取得的最大美学值。
状态转移方程为
规划方程为
（其中A(i,j)是花束i插在花瓶j中的美学值）
边界条件 （V是花瓶总数，事实上这是一个虚拟的边界）
<方法2>以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量sk表示前k个花瓶中放了多少花。而对于任意一个状态sk，决策就是第sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(sk)表示前k个花瓶中插了sk束花，所能取得的最大美学值。
状态转移方程为
规划方程为
边界条件为
两种划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了问题。只不过因为决策的选择有多有少，所以算法的时间复杂度也就不同。[2]
这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。
所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。
§2.2动态规划的模式性
这个可能做过动态规划的人都有体会，从我们上面对动态规划的分析也可以看出来。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。
选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
写出规划方程（包括边界条件）：在第一部分中，我们已经给出了规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。大体上的框架如下：
对f1(s1)初始化（边界条件）
for kß2 to n（这里以顺序求解为例）
对每一个skÎSk
fk(sk)ß一个极值（∞或－∞）
对每一个uk(sk)ÎDk(sk)
sk-1ßTk(sk,uk)
tßg(fk-1(sk-1),uk)
y t比fk(sk)更优 n
fk(sk)ßt
输出fn(sn)
这个N-S图虽然不能代表全部，但足可以概括大多数。少数的一些特殊的动态规划，其实现的原理也是类似，可以类比出来。我们到现在对动态规划的分析，主要是在理论上、设计上，原因也就在此。
掌握了动态规划的模式性，我们在用动态规划解题时就可以把主要的精力放在理论上的设计。一旦设计成熟，问题也就基本上解决了。而且在设计算法时也可以按部就班地来。
但是“物极必反”，太过拘泥于模式就会限制我们的思维，扼杀优良算法思想的产生。我们在解题时，不妨发挥一下创造性，去突破动态规划的实现模式，这样往往会收到意想不到的效果。[3]
§2.3动态规划的技巧性
上面我们所说的动态规划的模式性，主要指的是实现方面。而在设计方面，虽然它较为严格的步骤性，但是它的设计思想却是没有一定的规律可循的。这就需要我们不断地在实践当中去掌握动态规划的技巧，下面仅就一个例子谈一点我自己的体会。
[例3] 街道问题：在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。
这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：

按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量sk表示当前处于这一阶段上的哪一点（各点所对应的阶段和状态已经用ks在地图上标明）。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：

（这里的row是地图竖直方向的行数）
我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：
将地图中的点规则地编号如上，得到的规划方程如下：

（这里Distance表示相邻两点间的边长）
这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的“状态转移”就不全是在两个阶段之间进行的了。
也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种“简单”的方法就不太好办了。
如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径“不能重叠”的问题。
而我们回到原先“标准”的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用sk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑：

在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：

从这个例子中可以总结出设计动态规划算法的一个技巧：状态转移一般是在相邻的两个阶段之间（有时也可以在不相邻的两个阶段间），但是尽量不要在同一个阶段内进行。
动态规划是一种很灵活的解题方法，在动态规划算法的设计中，类似的技巧还有很多。要掌握动态规划的技巧，有两条途径：一是要深刻理解动态规划的本质，这也是我们为什么一开始就探讨它的本质的原因；二是要多实践，不但要多解题，还要学会从解题中探寻规律，总结技巧。
§3动态规划与一些算法的比较
动态规划作为诸多解题方法中的一种，必然和其他一些算法有着诸多联系。从这些联系中，我们也可以看出动态规划的一些特点。
§3.1动态规划与递推
——动态规划是最优化算法
由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。
按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。
[例4] mod 4 最优路径问题：在下图中找出从第1点到第4点的一条路径，要求路径长度mod 4的余数最小。
这个图是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般的多段图要简单，但是这个最优路径问题却不能用动态规划来做。因为一条从第1点到第4点的最优路径，在它走到第2点、第3点时，路径长度mod 4的余数不一定是最小，也就是说最优策略的子策略不一定最优——这个问题不满足最优化原理。
但是我们可以把它转换成判定性问题，用递推法来解决。判断从第1点到第k点的长度mod 4为sk的路径是否存在，用fk(sk)来表示，则递推公式如下：
（边界条件）

（这里lenk,i表示从第k-1点到第k点之间的第i条边的长度，方括号表示“或(or)”运算）
最后的结果就是可以使f4(s4)值为真的最小的s4值。
这个递推法的递推公式和动态规划的规划方程非常相似，我们在这里借用了动态规划的符号也就是为了更清楚地显示这一点。其实它们的思想也是非常相像的，可以说是递推法借用了动态规划的思想解决了动态规划不能解决的问题。
有的多阶段决策问题（像这一题的阶段特征就很明显），由于不能满足最优化原理等使用动态规划的先决条件，而无法应用动态规划。在这时可以将最优指标函数的值当作“状态”放到下标中去，从而变最优化问题为判定性问题，再借用动态规划的思想，用递推法来解决问题。
§3.2动态规划与搜索
——动态规划是高效率、高消费算法
同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。这其中有没有什么规则呢？
我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。所以动态规划可以解决的问题，搜索也一定可以解决。
把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都可以直接“移植”，所不同的只是求解顺序。动态规划是自底向上的递推求解，而搜索则是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。
反过来，我们也可以把搜索算法改写成动态规划。状态空间搜索实际上是对隐式图中的点进行枚举，这种枚举是自顶向下的。如果把枚举的顺序反过来，变成自底向上，那么就成了动态规划。（当然这里有个条件，即隐式图中的点是可排序的，详见下一节。）
正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。在搜索中，往往会出现下面的情况：
对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示，状态C2被搜索了两次。在深度搜索中，这样的重复会引起以C2为根整个的整个子搜索树的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小的。而动态规划就没有这个问题，如上图(c)所示。
一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。（当然对于某些题目，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。）而从理论上讲，任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态规划。但事实上，在很多情况下我们仍然不得不采用搜索算法。那么，动态规划算法在实现上还有什么障碍吗？
考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。在搜索算法中，这样的两个状态就不被考虑了，如上图(b)所示。但是动态规划由于是自底向上求解，所以就无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。
一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的事搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。
§3.3动态规划与网络流
——动态规划是易设计易实现算法
由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的图如多段图，或特殊的分段方法如Floyd），因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是有向无环图。
在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法[4]，已经体现出了简单的动态规划思想。但动态规划在图论中还有更有价值的应用。下面先看一个例子。
[例6] N个人的街道问题：在街道问题（参见例3）中，若有N个人要从左下角走向右上角，要求他们走过的边的总长度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目的地的三条路径，右图是他们所走过的边，这些边的总长度为5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维来表示，。相应的，决策变量也要变成N维，uk=(uk,1,uk,2,…,uk,N)。状态转移方程不需要做什么改动：

在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里我就用gk(sk,uk)来表示了：

边界条件为
可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法就不可能实现了。
下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是流量和边权的乘积 ，而是用下式计算：

为了使经典的费用流算法适用于本题，我们需要将模型稍微转化一下：
如图，将每条边拆成两条。拆开后一条边上有权，但是容量限制为1；另一条边没有容量限制，但是流过这条边就不能计算费用了。这样我们就把问题转化成了一个标准的最大费用固定流问题。
这个算法可以套用经典的最小费用最大流算法，在此就不细说了。（参见附录中的源程序）
这个例题是我仿照IOI97的“障碍物探测器”一题[6]编出来的。“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有99年冬令营的“迷宫改造”[7]。从这些题目中都可以看到动态规划和网络流的联系。
推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的变量sk=(sk,1,sk,2,…,sk,N)来描述状态，其中sk,iÎV(1£i£N)。相应的，决策也用N维的变量uk=(uk,1,uk,2,…,uk,N)来表示，其中uk,iÎE(sk,i)(1£i£N)，E(v)表示指向v的弧集。则状态转移方程可以这样表示：
sk-1,i = uk,i的弧尾结点
规划方程为
边界条件为
但是，由于动态规划算法是指数级算法，因而在实现中的局限性很大，仅可用于一些N非常小的题目。然而在竞赛解题中，比如上面说到的IOI97以及99冬令营测试时，我们使用动态规划的倾向性很明显（“障碍物探测器”中，我们用的是贪心策略，求N=1或N=2时的局部最优解[8]）。这主要有两个原因：
一． 虽然网络流有着经典的算法，但是在竞赛中不可能出现经典的问题。如果要运用网络流算法，则需要经过一番模型转化，有时这个转化还是相当困难的。因此在算法的设计上，灵活巧妙的动态规划算法反而要更为简单一些。
二． 网络流算法实现起来很繁，这是被人们公认的。因而在竞赛的紧张环境中，实现起来有一定模式的动态规划算法又多了一层优势。
正由于动态规划算法在设计和实现上的简便性，所以在N不太大时，也就是在动态规划可行的情况下，我们还是应该尽量运用动态规划。
§4结语
本文的内容比较杂，是我几年来对动态规划的参悟理解、心得体会。虽然主要的篇幅讲的都是理论，但是根本的目的还是指导实践。
动态规划，据我认为，是当今信息学竞赛中最灵活、也最能体现解题者水平的一类解题方法。本文内容虽多，不能涵盖动态规划之万一。“纸上得来终觉浅，绝知此事要躬行。”要想真正领悟、理解动态规划的思想，掌握动态规划的解题技巧，还需要在实践中不断地挖掘、探索。实践得多了，也就能体会到渐入佳境之妙了。
动态规划，
算法之常，
运用之妙，
存乎一心。

Ⅱ 数学建模网络流算法重要吗你们都用什么算法呢

1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，
同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）
2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，
而处理数据的关键就在于这些算法，通常使用matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，
很多时候这些问题可以用数学规划算法来描述，通常使用lindo、lingo软件实现）
4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，
涉及到图论的问题可以用这些方法解决，需要认真准备）
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法
（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，
但是算法的实现比较困难，需慎重使用）
7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，
当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）
8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）
9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比
如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）
10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，
这些图形如何展示以及如何处理就是需要解决的问题，通常使用matlab进行处理）

Ⅲ 一个网络流算法题

将原树树链剖分后建线段树。

对于每个旅行商从原点向旅行商连ci,旅行商向线段树对应区间连无穷。
城市向汇点连wi
最大流即可

Ⅳ 程序员必须掌握哪些算法

一.基本算法:

枚举. (poj1753,poj2965)

贪心(poj1328,poj2109,poj2586)

递归和分治法.

递推.

构造法.(poj3295)

模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.

最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)

二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)

排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

简单并查集的应用.

哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)

堆

trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)

型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学

组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.

几何公式.

叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:
一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)

较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)

最小费用最大流(poj2516,poj2516,poj2195)

双连通分量(poj2942)

强连通分支及其缩点.(poj2186)

图的割边和割点(poj3352)

最小割模型、网络流规约(poj3308)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

Ⅳ 网络流的资料

编辑本段定义
图论中的一种理论与方法，研究网络上的一类最优化问题 。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)
譬如图5-1就是一个网络流图。
1．可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1、 每一条弧(i,j)有fij≤cij。
2、 除源点S和汇点T以外的所有的点vi，恒有：
该等式说明中间点vi的流量守恒，输入与输出量相等。
3、 对于源点S和汇点T有：
这里V(f)表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下：
流量V(f) = 5。
2．可改进路
给定一个可行流f=。若fij = cij，称<vi, vj>为饱和弧；否则称<vi, vj>为非饱和弧。若fij = 0，称<vi, vj>为零流弧；否则称<vi, vj>为非零流弧。
定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
给定一个可行流f，P是从S到T的一条道路，如果满足：
那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。
3．割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
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），即：
例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。
通俗简明的讲：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流？首先它必须是一个可行流；其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下：
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。
对可改进路P上的弧<vi, vj>，分为两种情况讨论：
第一种情况：<vi, vj>∈P+，可以令fij增加一个常数delta。必须满足fij + delta ≤ cij，即delta ≤ cij – fij。
第二种情况：<vi, vj>∈P-，可以令fij减少一个常数delta。必须满足fij - delta ≥ 0，即delta ≤ fij
根据以上分析可以得出delta的计算公式：
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta > 0）。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？
答案是肯定的。下面我们给出证明。
定理1 可行流f是最大流的充分必要条件是：f中不存在可改进路。
证明：
首先证明必要性：已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。
再证明充分性：已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，则y∈U;
若x∈U，且fyx>0，则y∈U。
（这实际上就是可改进路的构造规则）
（c） W = V \ U。
由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U, W）。
按照U的定义，若x∈U，y∈W，则fxy = cxy。若x∈W，y∈U，则fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理：
最大流最小割定理：最大流等于最小割，即max V(f) = min C(U, W)。
至此，我们可以轻松设计出求最大流的算法：
step 1. 令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。
step 2. 若f中找不到可改进路则转step 5；否则找到任意一条可改进路P。
step 3. 根据P求delta。
step 4. 以delta为改进量，更新可行流f。转step 2。
step 5. 算法结束。此时的f即为最大流。
三、最小费用最大流
1．问题的模型
流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。
容易看出，此图的最大流（流量是8）为：fs1 = f1t = 5, fs2 = f2t = 3。所以它的费用是：3*5+4*5+7*3+2*3 = 62。
一般的，设有带费用的网络流图G = (V, E, C, W)，每条弧<Vi, Vj>对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：
(a) 流量V(f)最大。
(b) 满足a的前提下，流的费用Cost(f) = 最小。
就称f是网络流图G的最小费用最大流。
2．算法设计
我们模仿求最大流的算法，找可改进路来求最小费用最大流。
设P是流f的可改进路，定义 为P的费用（为什么如此定义？）。如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。
算法可描述为：
step 1. 令f为零流。
step 2. 若无可改进路，转step 5；否则找到最小费用可改进路，设为P。
step 3. 根据P求delta（改进量）。
step 4. 放大f。转step 2。
step 5. 算法结束。此时的f即最小费用最大流。
至于算法的正确性，可以从理论上证明。读者可自己思考或查阅有关运筹学资料。
2．最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。
设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f。我们构造带权有向图B = (V’, E’)，其中：
1、 V’ = V。
2、 若<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算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法。
设Short[k]表示从S到k顶点的最短路径长度；从S到顶点k的最短路径中，顶点k的前趋记为Last[k]。那么迭代算法描述如下：（为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1）
step 1. 令Short[k]  +∞（1≤k≤n+1），Short[0]  0。
step 2. 遍历每一条弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，则令Short[j]  Short[k] + <k, j>，同时Last[j]  k。倘不存在任何一条弧满足此条件则转step 4。
step 3. 转step 2.
step 4. 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。
3．思维发散与探索
1）可改进路费用：“递增！递增？”
设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？
2）迭代法：“小心死循环！嘿嘿……”
迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？
3）费用：“你在乎我是负数吗？”
网络流图中的费用可以小于零吗？
4）容量：“我管的可不仅是弧。”
网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？
四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧<Vi, Vj>加上一个下界限制Aij（即必须满足Aij≤fij）。
例如图5-9：
弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b)。
那么有上下界的网络最大流怎么求呢？
一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下：
设原网络流图为G = (V, E, C, A)，构造不含下界的网络流图G’ = (V’, E’, C’)：
1、 V’ = V∪{S’, T’}
2、 对每个顶点x，令 ，若h-(x)≠0，就添加一条弧<S’, x>，其上界为h-(x)。
3、 对每个顶点x，令 ，若h+(x)≠0，就添加一条弧<x, T’>，其上界为h+(x)。
4、 对于任何<Vi, Vj>∈E，都有<Vi, Vj>∈E’，其上界C’ij = Cij – Aij。
5、 新增<T, S>∈E’，其上界CTS = +∞。
在G’中以S’为源点、T’为汇点求得最大流f’。若f’中从S’发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正确性很容易证明，留给读者完成）
然后再求可改进路（反向弧<Vi, Vj>必须满足fij≥Aij，而非fij≥0），不断放大f，直到求出最大流。
我们看到，上几节所讨论的一种可行网络流实际上是{Aij = 0}的一种特殊网络流，这里提出的模型更一般化了。解决一般化的复杂问题，我们采取的思路是将其转化为特殊的简单问题，加以研究、推广，进而解决。这是一种重要的基本思想：化归——简单有效。基于这种思想，请读者自行思考解决：
1、 有上下界的最小流。
2、 有上下界的最小费用最大流。
五、多源点、多汇点的最大流
已知网络流图有n个源点S1、S2、……、Sn，m个汇点T1、T2、……、Tm，，求该图的最大流。这样的问题称为多源点、多汇点最大流。
它的解决很简单：
1、 增设一个“超级源”S’，对每个源点Si，新增弧<S’, Si>，容量为无穷大。
2、 增设一个“超级汇”T’，对每个汇点Ti，新增弧<Ti, T’>，容量为无穷大。
3、 以S’为源点、T’为汇点求最大流f。
4、 将f中的S’和T’去掉，即为原图的最大流。
算法正确性显然。
六、顶点有容量限制的最大流
上一节已经提出了这个问题，即对于进出每个顶点的流量也规定一个上限，这样的最大流如何求？
既然我们已经解决了“边限制”问题，现在何不把“点限制”问题转化为“边限制”呢？具体办法如下：
1、 对除源点和汇点之外的每个顶点i拆分成两个顶点i’和i’’。新增一条弧<i’, i’’>，其容量为点i的流量限制。
2、 对于原图中的弧<i, j>，我们将其变换成<i’’, j’>。
3、 对变换后的图求最大流即可。
这里我们又一次运用到了化归的思想：将未知的“点限制”问题转化为已知的“边限制”问题。
七、网络流与二部图的匹配
{二部图和匹配的定义可参见本书专门介绍二部图匹配的章节}
设二部图为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’为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。

复制的我快吐了~