2022年数学建模图论模型图论 .pdf

图论算法1 最小生成树11 生成树的概念设图 G(V，E)是一个连通图，当从图中任一顶点出发遍历图G 时，将边集E(G)分成两个集合A(G)和 B(G)。其中 A(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V，A)是图 G 的子图，则称子图G1 是连通图 G 的生成树。图的生成树不是惟一的。如对图1(a)，当按深度和广度优先搜索法进行遍历就可以得到图1 中(b)和(c)的两棵不同的生成树，并分别称之为深度优先生成树和广度优先生成树。对于有 n 个顶点的连通图，至少有n-1 条边，而生成树中恰好有n-1 条边，所以连通图的生成树是该图的极小连通子图。若图G 的生成树中任意加一条边属于边集B(G)中的边，则必然形成回路。求解生成树在许多领域有实际意义。例如，对于供电线路或煤气管道的铺设问题，即假设要把n 个城市联成一个供电或煤气管道网络，则需要铺设n1 条线路。任意两城市间可铺设一条线路，n 个城市间最多可能铺设 n(n 1)/2 条线路，各条线路的造价一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择 n-1 条使该网络的建造费用最少，这就是下面要讨论的最小生成树问题。1.2 网的最小生成树在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。假设，要在 n 个居民点之间敷设煤气管道。由于，在每一个居民点与其余n1 个居民点之间都可能敷设煤气管道。因此，在n 个居民点之间，最多可能敷设n(n-1)/2 条煤气管道。然而，连通n 个居民点之间的管道网络，最少需要n-1 条管道。也就是说，只需要n-1 条管道线路就可以把n 个居民点间的煤气管道连通。另外，还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在n(n-1)/2 条可能的线路中优选n-1 条线路，构成一个煤气管道网络，从而既能连通n 个居民点，又能使总的花费代价最小。解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点，把居民点之间的煤气管道看作边，而把敷设各条线路的代价当作权赋给相应的边。这样，便构成一个带权的图，即网。对于一个有 n 个顶点的网可以生成许多互不相同的生成树，每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。如何构造这种网的最小生成树呢?下面给出这样一种解法：(1)已知一个网，将网中的边按其权值由小到大的次序顺序选取。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 21 页 -(2)若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。(3)如此依次进行，直到选够(n-1)条边即得到最小生成树。现以图 2 为例说明此算法。设此图是用边集数组EV 表示的，且数组中各边是按权值由小到大的次序排列，如下表所示。k 1 2 3 4 5 6 7 8 9 10 EVk.p1 2 2 4 2 6 5 1 1 1 5 EVk.p2 3 4 3 6 4 7 5 6 2 6 COSTEVk.p1,EVk.p2 5 6 10 11 14 18 19 21 27 33 按权值由小到大选取各边就是在数组中按下标k 由 1 到 en(图中边数)的次序选取。选前2 条边(2，3)，(2，4)时均无问题，保留作为树的边；到第3 条边(4，3)时将与已保留的边形成回路，将其舍去；同样继续做：保留(2，6)；舍去(6，4)；保留(5，7)，(1，5)，(1，6)，此时，保留的边数已够(n-1)=6 条边，此时必定将 7 个顶点全部互相连通了，后面剩下的边(1，2)，(5，6)就不必再考虑了。最后得到的最小生成树如图 2a 中深色边所示，其各边权值总和等于80。由离散数学中的图论可以证明，这就是最小生成树了，其权值最小。当图中有权值相等的边时，其最小生成树可能有不同的选取方案。实现此算法的关键是，在选取某条边时应判断是否与已保留的边形成回路。这可用将各顶点划分为集合的办法解决：假设数组tag(1.en)作为顶点集合划分的标志初值为0。在算法的执行过程中，当所选顶点u，v 是连通的，则将相应位置的tagu，tagv 置以相同的数字，而不连通的点在初期分属不同的集合，置不同的数字；一旦两个不同的连通分支连通了，则修改tag 的值，将新的连通分支改为相同的数字。我们以图 2 为例。首先选(2，3)(2，4)边，由于是连通的，并且不出现回路。tag2:1，tag3:=tag4:=1是同一个集合A；选(6，2)边与 A 集合连通；tag6:=1；再选(5，7)与集合 A 不连通，tag5:tag7:2 构成另一集合B；选(1，5)边与集合 B 连通，tag 1:=2；此时，集合A 2，3，4，6；集合 B5，7，1；当选(1，6)边时，(1，6)与集合 A、集合 B 都连通，并且两个顶点分别属于两个不同的集合A、B，这使得集合A 与集合 B 通过边(1，6)连通。修改集合B 中 tag 的值，置为 1，即将集合 B 并入集合 A。边为 n-1 条，这就是一棵最小生成树。根据集合标志数组tag 的变化过程，很容易判断，选择一条新的边是否构成回路。当新选边的两个顶点u、v，若 tagu 和 tagv 相同并且均不等于0 时，即 u，v 已在生成树集合中被保留过，加入u，v 后即形成回路，不能选。而当tag utagv 或者 tagu tagv 0 时，可以选并且不形成回路，说明u，v 中至少有一个顶点未被选过或者被选过的u、v 分别属于两个不同的集合，此时选择u，v 可以将含 u 的集合与含 v 的集合连通，修改tag 数组。如此下去，到所有顶点均已属于一个集合时，此最小生成树就完全构成了。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 21 页 -网的最小生成树算法描述 如下：假设算法中用到的数据结构是经过处理的。COST(1.n，1.n)是带权数组存放网中顶点之间的权。EV(1.n*(n-1/2)按权从小到大存放排序后的顶点对，即 EVK.P1存放一个顶点，边的另一顶点存放在EVK.P2 之中。tag(1.n)：顶点集合划分标志的数组。Enumb：当前生成树的边数。SM：当前权累计和。PROC minspanningtree(VAR cost；VAR ev)；Var tag；BEGIN CALL INITIAL(tag);Enumb：0；SM:=0;诸参量初始化 k:=1;边数累计 WHILE(Enumb=n-1)AND(kn)DO Begin U:=EVk.P1；V:=EVk.P2；选一对顶点(U，V)CALL FIND(U，T)；找到含顶点U的集合 T CALL FIND(V，W)；找到含顶点V的集合 W IF(TW)THEN Begin write(u，v)；Enumb:=Enumb+1；最小生成树增加一条边 SM:=SM+COSTu，v；MERGE(T，W)；选 u，v 不会形成环，合并T，W集合，并修改tag end K:=K+1;找下一条边 end IF Enumbw 表示从城市 v 到城市 W 的航线，弧 Vw 上的标号代表从V 城飞到 w 城所需要的时间。要寻找由该航空图上一给定城市到另一城市所需要的最短飞行时间。可以用求解这个有向图的单源最短路径算法来完成。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 21 页 -下面，我们讨论求解单源最短路径问题的贪心算法，也称Dijkstra 算法。设有向图 G=(V，E)，其中，V=1，2，n)cost 是表示 G 的邻接矩阵，costi，j表示有向边(i，j)的权。若不存在有向边(i，j)，则 costi，j的权为无限大(oo)。令 S 是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。(1)令顶点 V0 为源点，集合S 的初态只包含顶点V0，即 S=V0。数组 dist 记录从源点到其他各顶点当前的最短距离，其初值为disti:=costv0，i，(i=2，n)。(2)从 S 之外的顶点集合V-S 中选出一个顶点W，使 distW 的值最小。于是，从源点到达W 只通过 S中的顶点，我们把W 加入集合 S。(3)调整 dist 中记录的从源点到V-S 中每个顶点V 的距离：从原来的distv 和 distw+costw，v中选择较小的值作为新的distv。(4)重复上述过程(2)和（3），直到 S 中包含 V 的全部顶点。最终数组 dist 记录了从源点到V 中其余各顶点的最短路径。对图 3 所示的加权有向图应用Dijkstra 算法，从源点V2 出发到达各顶点的最短路径如下表所示。最短路径 -源点中间顶点终止顶点长度 2 5 10 3 15 3 4 30 3 1 35 6 oo -对图 3 的执行过程：初始时，S2，dist1 oo，dist315，dist4 oo，dist510，dist6 oo，第一遍处理时，W2 使 dist5 最小、于是把 5 加入 S。然后，调整 dist 中从源点到其余各顶点的距离：dist315，为次小，将3 加入 S。dist4cost2，3+cost3，4=15+15 30，经中间点3。S2，5，3，4，同理，dist1 cost2，3+cost3，135，S2，5，3，4，1，由于 2 没有一条到 6 的路径，所以 dist6=oo。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 21 页 -由此我们给出最短路径算法如下PROC shortpath(VAR cost；VAR dist；VAR path；VAR S，V0)；BEGIN FOR W:=1 TO n DO Begin distW:=costV0，W;最短路径初始化值 IF costV0，Wmax THEN pathW:=V0；path 记载当前最短路径 End;S:=V0;Vnum:=1；到达点集合S 和到达点 S 个数初值 WHILE(Vnumn-1)DO 最后一点已无选择余地 Begin Wm:=max；u:=V0;FOR W:=1 TO n DO IF(NOT W IN S)AND(distWWm)THEN Begin U:=W；Wm:=distw End;找最小 distw S:=S+U;Vnum:=Vnum+1;U为找到最短路径的终点 FOR W:=1 TO n DO IF(NOT W IN S)AND(distU+costU，WdistW)THEN Begin distW:=distU+costU，W;调整非 S 集各点最短路径值 pathW:=U；调整非 S 集各点最短路径 End;Vnum:=Vnum+1 End;END；PROC PRINTPATH(VAR dist VAR path；VAR S；V0)BEGIN FOR i:=1 TO n DO IF(i IN S)THEN Begin k:=i;WHILE(kV0)DO Begin write(k)；k:=pathk End;通过找前趋点，反向输出最短路径 write(k)；writeln(disti)End;ELSE Begin write(i，V0)；writeln(max)End;END；容易看出，算法short path 的时间复杂度为O(n2)，空间复杂度为O(n)。3 拓扑排序本节说明了如何用深度优先搜索，对一个有向无回路图进行拓扑排序。有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G 包含(u,v)，则在序列中u 出现在 v 之前（如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 21 页 -有向无回路图经常用于说明事件发生的先后次序，图 1 给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物(如先穿袜子后穿鞋)，也有一些衣物可以按任意次序穿戴(如袜子和短裤)。图 1(a)所示的图中的有向边(u,v)表明衣服 u 必须先于衣服v 穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列，使得图中所有有向边均从左指向右。下列简单算法可以对一个有向无回路图进行拓扑排序。procedure Topological_Sort(G);begin 1.调用 DFS(G)计算每个顶点的完成时间fv;2.当每个顶点完成后，把它插入链表前端;3.返回由顶点组成的链表;end;图 1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为(V+E)，每一个 v 中结点插入链表需占用的时间为(1)，因此进行拓扑排序的运行时间(V+E)。图 1 早晨穿衣的过程为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。引理 1 有向图 G 无回路当且仅当对G 进行深度优先搜索没有得到反向边。证明：名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 21 页 -：假设有一条反向边(u,v)，那么在深度优先森林中结点v 必为结点 u 的祖先，因此G 中从 v 到 u 必存在一通路，这一通路和边(u,v)构成一个回路。：假设 G 中包含一回路C，我们证明对G 的深度优先搜索将产生一条反向边。设v 是回路 C 中第一个被发现的结点且边(u,v)是 C 中的优先边，在时刻dv从 v 到 u 存在一条由白色结点组成的通路，根据白色路径定理 可知在深度优先森林中结点u 必是结点 v 的后裔，因而(u,v)是一条反向边。(证毕)定理 1 Topological_Sort(G)算法可产生有向无回路图G 的拓扑排序。证明:假设对一已知有问无回路图G=(V,E)运行过程 DFS 以确定其结点的完成时刻。那么只要证明对任一对不同结点 u,v V，若 G 中存在一条从u 到 v 的有向边，则fvfu 即可。考虑过程DFS(G)所探寻的任何边(u,v)，当探寻到该边时，结点v 不可能为灰色，否则v 将成为 u 的祖先，(u,v)将是一条反向边，和引理1 矛盾。因此，v 必定是白色或黑色结点。若v 是白色，它就成为u 的后裔，因此fvfu。若 v 是黑色，同样 fvfu。这样一来对于图中任意边(u,v)，都有 fvfu，从而定理得证。（证毕）另一种拓扑排序的算法基于以下思想：首先选择一个无前驱的顶点（即入度为0 的顶点，图中至少应有一个这样的顶点，否则肯定存在回路），然后从图中移去该顶点以及由他发出的所有有向边，如果图中还存在无前驱的顶点，则重复上述操作，直到操作无法进行。如果图不为空，说明图中存在回路，无法进行拓扑排序；否则移出的顶点的顺序就是对该图的一个拓扑排序。下面是该算法的具体实现：procedure Topological_Sort_II(G);begin 1 for 每个顶点 uVG do du0;/初始化 du,du 用来记录顶点u 的入度2 for 每个顶点 uVG do 3 for 每个顶点 vAdju do dvdv+1;/统计每个顶点的入度4 CreateStack(s);/建立一个堆栈s 5 for 每个顶点 uVG do 6 if du=0 then push(u,s);/将度为 0 的顶点压入堆栈7 count 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 21 页 -8 while(not Empty(s)do begin 9 utop(s);/取出栈顶元素10 pop(s);/弹出一个栈顶元素11 count count+1;12 Rcountu;/线性表 R 用来记录拓扑排序的结果13 for 每个顶点 vAdju do/对于每个和u 相邻的节点v begin 14 dv dv-1;15 if dv=0 then push(v,s);/如果出现入度为0 的顶点将其压入栈end;end;16 if countG.size then writeln(Error!The graph has cycle.)17 else 按次序输出 R;end;上面的算法中利用du 来记录顶点 u 的入度，第 2-3 行用来统计所有顶点的入度，第 5-6 行将入度为0的顶点压入堆栈，第 8-15 行不断地从栈顶取出顶点，将该顶点输出到拓扑序列中，并将所有与该顶点相邻的顶点的入度减1，如果某个顶点的入度减至0，则压入堆栈，重复该过程直到堆栈空了为止。显而易见该算法的复杂度为O(VE)，因为第 2-3 行的复杂性就是O(VE)，后面 8-15 行的复杂性也是O(VE)。这个算法虽然简单，但是没有前面一个算法 的效率高。4 网络流算法：概念名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 21 页 -在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50 年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立 个网络流模型，然后用最大流算法高效地解决问题。问题描述 如图 4-1 所示是联结某产品地v1 和销售地 v4 的交通网，每一弧(vi,vj)代表从 vi 到 vj 的运输线，产品经这条弧由vi 输送到 vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到 v4。现在要求制定一个运输方案使从v1 到 v4 的产品数量最多。图 4-1 图 4-2 一、基本概念及相关定理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)容量约束：0fijcij，(vi,vj)E，(2)守恒条件对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流 f，称为网络N 上的 可行流，并将源点 s 的净流量称为流f 的流值 v(f)。网络 N 中流值最大的流f*称为 N 的最大流。3)可增广路径所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。定义 3 设 f 是一个可行流，P 是从源点s 到汇点 t 的一条路，若p 满足下列条件：名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 21 页 -(1)在 p 上的所有前向弧(vivj)都是非饱和弧，即0fijcij(2)在 p 上的所有后向弧(vivj)都是非零弧，即00，再令：f*ij=f*ij+Q (vi，vj)P 的前向弧的集合f*ij=f*ij-Q (vi，vj)P 的后向弧的集合f*ij=f*ij(vi，vj)不属于 P 的集合不难证明 f*ij是可行流，且v(f*)=v(f*)+Qv(f*)。这与 f*是最大流假设矛盾，必要性证毕。证明 充分性：设 N 中不存在关于f*的增广路径，证明f*是最大流。我们利用下面的方法来定义A*。令 vs A*若 vi A*，且 fij0，则令 vj A*。因为不存在关于f*的增广路径，故vt不属于 A*。记 A*-=V-A*，于是得到一个割(A*，A*-)，显然有f*ij=cij，(vi，vj)(A*，A*-)f*ij=0，(vi，vj)(A*-，A*)所以 v(f*)=c(A*，A*-)。于是 f*必是最大流，定理得证。由上述证明中可得，若f*是最大流，则网络中必存在一个割集c(A*，A*-)，使得 v(f*)=c(A*，A*-)。于是有以下重要定理。定理 2 最大流最小割定理：在一个网络N 中，从 vs 到 vt 最大流的容量等于分离vs，vt 的最小割的容量。二最大网络流最大流问题实际上是求一可行流fij，使得 v(f 达到最大。定理1 中证明实际上已为我们提供了寻求网络中最大流的一个方法。若给了一个可行流f，只要判断N 中有无关于f 的增广路径，如果有增广路径，则按定理 1 的必要性证明中的办法，改进f，得到一个沈量增大的新的可行流；如果没有增广路径，则得到最大流。而利用定理1 充分性证明中定义A*的办法，可以根据vt 是 否属于 A*来判断 N 中有无关于f 的增广路径。下面我们用顶点标号法来定义A*，在标号过程中，有标号的顶点表示是A*中的点，没有标号的点表示名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 21 页 -不是 A*中的点。如果 vt 有标号，则说明找到了一条增广路径；如果标号过程进行不下去，而vt 又还没有标号，则说明不存在增广路径，于是得到了最大流，同时也得到了一个最小割集。1)寻求最大流的标号法(Ford,Fulkerson)从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f 的可增广路径为止。(1)标号过程在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个部分：第一标号表明它的标号从哪一点得到的，以便从vt 开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。标号开始时，给vs 标上(s，0)，这时 vs 是标号但末检查的点，其余都是未标号的点，记为(0，0)。取一个标号而未检查的点vi，对于一切未标号的点vj：A对于弧(vi，vj)，若 fij0，则给 vj 标号(-vi，0)，这时，vj 点成为标号而未检查的点。于是 vi 成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦 vt 被标上号，表明得到一条从 vi 到 vt 的增广路径p，转入调整过程。若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。(2)调整过程从 vt 点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设 vt 的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk)是 p 上弧。接下来检查vk 的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi)。再检查 vi 的第一标号，依此类推，直到vs 为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：Q=minmin(cij-fij)，minf*ij 对流 f 进行如下的修改：fij=fij+Q (vi，vj)P 的前向弧的集合fij=fij-Q (vi，vj)P 的后向弧的集合fij=f*ij(vi，vj)不属于 P的集合接着，清除所有标号，对新的可行流f，重新进入标号过程。2)求最大流标号法的具体实现(1)数据结构对于网络 N，它首先是一个有向图N(V，E)，对于有向图一般我们用邻接矩阵表示，为了存放流f，这个有向图的弧上信息包含两个部分，分别是弧的容量与弧上的流。具体的数据结构如下：type nettype=record c，f：integer；end；var g：arrayO.maxn,O.maxn of nettype；为了找到增广路径，我们要有对每个的顶点标号，第一个标号L 表明它的标号从哪一点得到的，第二标号 p 是为了表示该顶点是否已检查过。具体数据结构如下：type nodetype=record l，p：integer；名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 21 页 -end；var Lt：arrayO.maxn of nodetype；(2)参考程序Program Max_Stream;Const Maxn=20;type nettype=record C,F:integer;end;nodetype=record L,P:integer;end;var Lt:arrayO.maxn of nodetype;G:Array0.Maxn,0.Maxn of Nettype;N,S,T:integer;F:Text;Procedure Init;初始化过程，读人有向图，并设置流为0 Var Fn:String;I,J:Integer;Begin Write(Graph File=);Readln(Fn);Assign(F,Fn);Reset(F);Readln(F,N);Fillchar(G,Sizeof(G),0);Fillchar(Lt,Sizeof(Lt),O);For I:=1 To N Do For J:=1 To N Do Read(F,GI,J.C);Close(F);End;Function Find:Integer;寻找已经标号未检查的顶点 Var I:Integer;Begin I:=1;While(I=N)And Not(LtI.L0)And(LtI.P=0)Do Inc(I);If IN Thru Find:=0 Else Find:=I;End;Function Ford(Var A:Integer):Boolean;Var 用标号法找增广路径，并求修改量 I,J,M,X:Integer;名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 21 页 -Begin Ford:=True;Fillchar(Lt,Sizeof(Lt),0);LtS.L:=S;Repeat I:=Find;If i=0 Then Exit;For J:=1 To N Do If(LtJ.L=0)And(GI,J.C0)or(GJ,I.C0)Then Begin if(GI,J.F0)Then LtJ.L:=I;End;LtI.P:=1;Until(LtT.L0);M:=T;A:=Maxint;Repeat J:=M;M:=Abs(LtJ.L);If LtJ.L0 Then X:=GM,J.C-GM,J.F;If XA Then A:=X;Until M=S;Ford:=False;End;Procedure Change(A:Integer);调整过程 Var M,J:Integer;Begin M:=T;Repeat J:=M;M:=Abs(LtJ.L);If LtJ.L0 Then GM,J.F:=GM,j.F+A;Until M=S;End;Procedure Print;打印最大流及其方案 VAR I,J:Integer;Max:integer;Begin Max:=0;For I:=1 To N DO Begin If GI,T.F0 Then Max:=Max+GI,T.F;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 21 页 -For J:=1 To N Do If GI,J.F0 Then Writeln(I,-,J,GI,J.F);End;Writln(TheMaxStream，Max)；End；Procedure Process；求最大流的主过程 Var Del：Integer；Success:Boolean；Begin S:=1;T:=N;Repeat Success:=Ford(Del);If Success Then Print Else Change(Del);Until Success;End;Begin Main Program Init;Process;End.源程序 及数据文件 以上标号法求最大流的算法，只能适用于网络中的任意两点之间只有一条弧的情况，若任意两点之间有多条弧，则我们可以通过在这些弧中的每条弧上设置一个虚拟点，转化成任意两点间只有一条弧情况。三最小费用最大流上面的网络，可看作为辅送一般货物的运输网络，此时，最大流问题仅表明运输网络运输货物的能力，但没有考虑运送货物的费用。在实际问题中，运送同样数量货物的运输方案可能有多个，因此从中找一个输出费用最小的的方案是一个很重要的问题，这就是最小代价流所要讨论的内容。1)最小费用最大流问题的模型给定网络 N=(V，E，c，w，s，t)，每一弧(vi,vj)属于 E 上，除了已给容量cij外，还给了一个单位流量的费用 w(vi,vj)O(简记为 wij)。所谓最小费用最大流问题就是要求一个最大流f，使得流的总输送费用取最小值。W(f)=wijfij2)用对偶法解最小费用最大流问题最小费用流问题的常用算法有两种：原始算法与对偶算法，下面只介绍对偶算法。定义：已知网络 N=(V，E，c，w，s，t)，f 是 N 上的一个可行流，p 为 vs 到 vt(关于流 f)的可增广路径，称 W(p)=wij（p+）-wij（p-）为路径 p 的费用。若 p*是从 vs 到 vt 所有可增广路径中费用最小的路径，则称p*为最小费用可增广路径。定理：若 f 是流量为v(f)的最小费用流，p 是关于 f 的从 vs 到 vt 的一条最小费用可增广路径，则f 经过p 调整流量 Q 得到新的可行流f(记为 f=f+Q)，一定是流量为v(f)+Q 的可行流中的最小费用流。(证明参见名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 21 页 -有关运筹学资料)由于 wij0，f=0 就是流量为0 的最小费用流(费用也为 0)，所以初始最小费用流可以取f=0。(1)对偶法的基本思路取 f=0 寻找从 vs 到 vt 的一条最小费用可增广路径p。若不存在 p，则 f 为 N 中的最小费用最大流，算法结束。若存在 p，则用求最大流的方法将f 调整成 f*，使 v(f*)=v(f)+Q，并将 f*赋值给 f，转。(2)迭代法求最小费用可增广路径在前一节中，我们已经知道了最大流的求法。在最小费用最大流的求解中，每次要找一条最小费用的增广路径，这也是与最大流求法唯一不同之处。于是，对于求最小费用最大流问题余下的问题是怎样寻求关于 f 的最小费用增广路径p。为此，我们构造一个赋权有向图b(f)，它的顶点是原网络N 中的顶点，而把N中每一条弧(vi，vj)变成两个相反方向的弧(vi，vj)和(vj，vi)。定义 w(f)中的弧的权如下：如果(fij0)，则 bji=-wij；如果(fij=cij)，则 bji=+oo于是在网络N 中找关于 f 的最小费用增广路径就等价于在赋权有向图b(f)中，寻求从vs 到 vt 的最短路径。求最短路有三种经典算法，它们分别是Dijkstra 算法、Floyd 算法和迭代算法。由于在本问题中，赋权有向图b(f)中存在负权，故我们只能用后两种方法求最短路，其中对于本问题最高效的算法是迭代算法。为了程序的实现方便，我们只要对原网络做适当的调整。将原网络中的每条弧(vi，vj)变成两条相反的弧：前向弧(vi,vj)，其容量 cij和费用 wij不变，流量为fij；后向弧(vj,vi)，其容量 0 和费用-wij，流量为-fij。事实上，对于原网络的数据结构中，这些单元已存在，在用标号法求最大流时是闲置的。这样我们就不必产生关于流f 的有向图 b(f)。同时对判断(vi,vj)的流量可否改时，可以统一为判断是否“fij0，则 fji=-fij0=cji。除此，为了求vs 到 vt 的最短路径，设置一个数组best，其中结构如下。type Tbest=record value，fa：integer；end；var best：array1.maxN)of Tbest；besti.value表示 vs 到 vi 的最短距离，besti.fa 记录着 vs 到 vi 最短路径中vi 的前趋顶点，以便于找到从vs 到 vt 的增广路径。在每一次寻找最小费用可增广路径前，vs 的 value 值设为 0，其它顶点的value 值设为 MaxInt。迭代法求最短增广路径的具体算法如下：Best 赋初值(除源点的 value 值为 0，其余点的value 值均为 MaxInt)repeat Quit:=True；for i:=1 to n do if 源点到 i 有道路then for j:=1 to n do if(vi，vj)的流量可改进)and(i 的 value 值+(vi，vj)j 的 value 值)then begin j 的 value 值:=i 的 value 值+(vi,vj);j 的 fa 值:=i;名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 21 页 -Quit:=false；end；until Quit；(3)流的调整若找到 vs 到 vt 的最小费用可增广路径，则我们可以从bestt.fa 开始反向跟踪找到整个从源点到汇点的可增广路径 p，然后修改可增广路的流量，改进量Q=min|fij|；(vi，vj)p。注意，在修改增广路上的弧(vi,vj)的流量 fij 后，还要修改狐(vj,vi)的流量 fji(fji=-fij)。为了简化程序设计，下面的改进流的过程Add-Path，仅以 1 作为改进量。procedure Add_Path；var i,j:integer;begin i:=t;while is do begin j:=beati.fa；inc(Netj，i.f)；Neti，j.f:=-Netj，i.f;i:=j;end；inc(Minw，bestt.value)；end；下面请大家编出求最小费用最大流的程序。程序要求的输入文件的格式如下：文件的第一行有两种整数N，表示网络中顶点数。第二行开始，每行描述网络中的一条弧的信息i，j，cij，wij，分别表示弧的起点与终点以及弧上的容量与单位流量通过该弧的费用。文件以连续的4 个 0 表示输入结束。四网络流算法的应用网络流算法的效率为大约为O(E2 V(f*)，其中 E 为网络中弧的数目，v(f*)为最大流的流值。因此网络流算法效率是多项式算法，仍然是个高效算法。在近年的竞赛中，网络流算法的应用越来越广，但竞赛中的问题大都看起来与流的问题似乎不相关。只要我们能构造出问题的网络流模型，就能应用流的算法高效的解决问题。例 1 最优工作问题(work)CCS 集团有 n 台机器。为了生产需要，新招募了n 名技术人员。他们有丰富的专业技术，每个人都熟悉各种机器的操作。现在每个人只能操作一台机器，而每个人对不同机器的控制能力又有差别，技术员 i 对机器 j 的控制能力称为ability(i，j)。要求给每人分配一台机器，使得所有人控制能力之和最大。输入格式：第一行仅有一个整数n(n=100)，第二行开始是一个n*n 的矩阵，第 i 行第 j 列表示 ability(i，j)(ability(i，j)=300)。输出格式：仅一行：包含一个整数S，表示最大控制能力和。样例：INPUT TXT 3 5 2 3 2 8 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 21 页 -7 5 8 OUTPUT TXT 20 问题分析 对于本问题，可以建立如图4-3 所示的图，x1，x2，x3 分别代表