(6)构造增量网络N(∫3),并找N(f3)中的负费用圈 (1,2) 12)1-1)(25) 增量网络N(y,每条弧上的二元数组 分别表示(c,w)。其中无负费用圈 因N(∫3)中已无负费用圈,故∫3是最小费用3值流。 注:(1)如果网络N中的弧容量全为整数,且w是非负整数,则负费用有向圈算法在有限步结束 (2)在N(中找负费用圈可利用求最短路的 Floyd算法 、求最小费用流的最小费用路算法 定理9.42设∫是网络N=(V,x,y,A,C,w)上的一个最小费用流,其流值为V0,P是N中一条最 小费用x-y路,δ是P上最小的弧容量,日是满足6≤d的一个常数,则沿P对∫增流θ后所得的流∫ 是N的流值为V(0+θ的最小费用流。 证明:略 由上述定理可得求最小费用流的最小费用路算法 求最小费用流的最小费用路算法 输入:N(,x,y,A,C,w), 输出:N中流值为V的最小费用流 Step0.取零流作为初始可行流f。 Stepl.若val′=Vo,则停止,当前的∫即为所求的最小费用流,输出f;否则,转下步。 Step2.构造增量网络N(∫)。若N(f)中不存在x-y有向路,则N中无流值为V的可行流,停止;否 则,找出N(/)的一条最小费用有向路P,转下步。 Step3.用c(P表示P上最小的弧容量,令日=min{c(p),V-Fal},沿P对∫增流,得新流 转 Stepl 四、求最小费用最大流的算法 问题:求网络N(V,x,y,A,C,w)中的一个费用最小的最大流。 算 输入:N(V,x,y,A,C,w) 输出:N中流值为v的最小费用流 Step0.取零流作为初始可行流f。(6) 构造增量网络 N( f 3 )，并找 N( f 3)中的负费用圈。 因 N( f 3)中已无负费用圈，故 f 3是最小费用 3 值流。 注：（1）如果网络 N 中的弧容量全为整数，且 v0是非负整数，则负费用有向圈算法在有限步结束。 （2）在 N(f)中找负费用圈可利用求最短路的 Floyd 算法。 三、求最小费用流的最小费用路算法 定理 9.4.2 设 f 是网络 N V x y AC w = (,,,, , ) 上的一个最小费用流，其流值为 V(f)，P 是 N(f) 中一条最 小费用 x-y 路，δ 是 P 上最小的弧容量，θ 是满足θ ≤ δ 的一个常数，则沿 P 对 f 增流θ 后所得的流 f ′ 是 N 的流值为 V(f) +θ 的最小费用流。 证明：略 由上述定理可得求最小费用流的最小费用路算法。 求最小费用流的最小费用路算法 输入： NV x y AC w (,,, , , ) ，V0 输出：N 中流值为 V0的最小费用流。 Step 0. 取零流作为初始可行流 f。 Step1. 若 Val f= V0，则停止，当前的 f 即为所求的最小费用流，输出 f；否则，转下步。 Step 2. 构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，则 N 中无流值为 V0的可行流，停止；否 则，找出 N( f )的一条最小费用有向路 P，转下步。 Step 3. 用 c(P)表示 P 上最小的弧容量，令 min{ ( ), } 0 θ = c p V Valf − ，沿 P 对 f 增流θ ，得新流 f， 转 Step1 。 四、求最小费用最大流的算法 问题：求网络 NV x y AC w (,,, , , ) 中的一个费用最小的最大流。 算法： 输入： NV x y AC w (,,, , , ) ， 输出：N 中流值为 V0的最小费用流。 Step 0. 取零流作为初始可行流 f。 增量网络 N(f 3)，每条弧上的二元数组 分别表示 (c′, w′ )。其中无负费用圈。 (1,−2) (1,2) (3,4) (1,−1) (3,1) (2,5) x y (2,−3) (3,−2)