解:(1)用最大流算法求流值为3的可行流∫ 网络N的一个可行流∫,每条弧 上的三元数组分别表示,(c,w) (2)构造增量网络N(f),并找N(f)中的负费用圈 (2,-2 (1.4) (1,1) 增量网络N及其一个负费用圈(虚线所示) 每条弧上的二元数组分别表示(c,w) (3)沿负费用圈修改流,得N中新的3值流∫2。 1,(3,4) 2(2,2) (4)构造增量网络N(∫2),并找N(/2)中的负费用圈。 (2,-2 (2,5) 增量网络N5及其一个负费用圈(虚线所示), 每条弧上的二元数组分别表示(c;w) (5)沿负费用圈修改流,得新的3值流∫3 0(34解：(1) 用最大流算法求流值为 3 的可行流 f1: (2) 构造增量网络 N( f1 )，并找 N( f1 )中的负费用圈。 (3) 沿负费用圈修改流，得 N 中新的 3 值流 f 2。 (4) 构造增量网络 N( f 2 )，并找 N( f 2)中的负费用圈。 (5) 沿负费用圈修改流，得新的 3 值流 f 3。 网络 N 的一个可行流 f ，每条弧 上的三元数组分别表示 f, (c, w)。 2,(2,2) 1,(2,3) 2,(3,4) 0,(1,1) 2,(3,1) 0,(2,5) 1,(3,2) x y 增量网络 N(f 1) 及其一个负费用圈(虚线所示)， 每条弧上的二元数组分别表示 (c′, w′ )。 (2,−2) (1,3) (1,4) (1,1) (1,1) (2,5) (2,2) x y (1,−3) (1,−2) (2,−1) (2,−4) 增量网络 N(f2)及其一个负费用圈(虚线所示)， 每条弧上的二元数组分别表示 (c′, w′ )。 (2,−2) (1,3) (2,4) (1,−1) (2,1) (2,5) (1,2) x y (1,−3) (2,−2) (1,−1) (1,−4) 2,(2,2) 1,(2,3) 1,(3,4) 1,(1,1) 1,(3,1) 0,(2,5) 2,(3,2) x y 1,(2,2) 2,(2,3) 0,(3,4) 1,(1,1) 0,(3,1) 0,(2,5) 3,(3,2) x y