Stepl.构造增量网络N(∫)。若N(∫)中不存在x-y有向路,则当前的∫即为所求的最小费用最大流 输出;否则,找出N(f)的一条最小费用有向路P,转下步。 Step2.沿P对∫增流,得新的可行流f,转 Stepl。 五、求总费用限定的最大流的算法 问题:对网络N(V,x,y,A,C,w)和一个预定的总费用值v≥0,求N中总费用不超过的一个 流,使其流值在所有这样的流中达到最大。 算法: 输入:N(,x,y,A,C,w); 输出:费用≤wn的流中流值最大的流 Step0.取零流作为初始可行流f。 Step I.构造增量网络N(∫)。若N(∫)中不存在x-y有向路,转Step4;否则,找出N(f)的一条最小费 用xy有向路P,转下步。 Step2若w'(P)>0,则令 8=min(c(P) ,(c(P)表示P上最小弧容量) 转Step3:否则沿P对∫增流,得新的可行流f,转 Stepl Step3若θ=0,则停止,当前的∫便是N中费用不超过v的最大流,输出f;否则沿P对∫增流值 6,得新的可行流f,转 Stepl 第九章习题 在下面的网络中,弧上第一个数字表示流量,第二个数字表示容量 (1)确定所有的割 3(3) (2)求最小割的容量; 1(3)01 (3)证明给定流是最大流。 3(4) 2(2) 2若(S,S)和(T7)都是N中的最小割,证明(SUT,S∪T)及(S∩7,S∩T)也都是N的最小割 3.对如下网络,从零流开始,分别用Ford- Fulkson标号算法和 Dinic算法求出其最大流,写出或画出算 法过程。(注:括号内数字表示弧的容量,括号外数字表示当前流值)。 0(7) 10)Step1. 构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，则当前的 f 即为所求的最小费用最大流， 输出 f；否则，找出 N( f )的一条最小费用有向路 P，转下步。 Step 2. 沿 P 对 f 增流，得新的可行流 f，转 Step1 。 五、求总费用限定的最大流的算法 问题：对网络 NV x y AC w (,,, , , ) 和一个预定的总费用值 0 w ≥ 0 ，求 N 中总费用不超过 w0 的一个 流，使其流值在所有这样的流中达到最大。 算法： 输入： NV x y AC w (,,, , , ) ； w0 。 输出：费用≤ w0 的流中流值最大的流。 Step 0. 取零流作为初始可行流 f。 Step 1. 构造增量网络 N( f )。若 N( f )中不存在 x-y 有向路，转 Step 4；否则，找出 N( f )的一条最小费 用 x-y 有向路 P，转下步。 Step 2 若 w P′( ) > 0 ，则令 ( ) min{ ( ), } ( ) w wf 0 c P w P θ − = ′ ′ ，（c P′( ) 表示 P 上最小弧容量）， 转 Step3；否则沿 P 对 f 增流，得新的可行流 f，转 Step1。 Step 3 若θ = 0，则停止，当前的 f 便是 N 中费用不超过 w0 的最大流，输出 f；否则沿 P 对 f 增流值 θ ，得新的可行流 f，转 Step1。 第九章习题 1. 在下面的网络中，弧上第一 个数字表示流量，第二个数字表示容量。 (1) 确定所有的割； (2) 求最小割的容量； (3) 证明给定流是最大流。 2. 若(, ) S S 和(, ) T T 都是 N 中的最小割，证明(, ) S TS T ∪ ∪ 及(, ) S TS T ∩ ∩ 也都是 N 的最小割。 3. 对如下网络，从零流开始，分别用 Ford-Fulkson 标号算法和 Dinic 算法求出其最大流，写出或画出算 法过程。（注：括号内数字表示弧的容量，括号外数字表示当前流值）。 x y 0(8) 0(7) 0(9) 0(5) 0(2) 0(9) 0(10) 0(5) v1 v3 1(3) 3(4) 3(3) 0(1) 2(5) 2(2) x y v2 2(2)