7 (4,10 ”9 ⑨ (2,5)(6,2)(2,4) (1,8) 4 4 (3,10) (i) 可行流f4:vf4)=11 (a)费用、容量网络 图7-17 ① (7)构造关于f的有向费用网络 W(f),如图7-17(j)所示： -2 由于在W(f)中无法找到从→ 的最短路，所以∫4就是该网终的最 小费用最大流，流量(f)=1,其 -3 分布情况如图7-17()所示。它对 (j)费用网络W(f) 应的总费用为： b()=4×3+1×7+1×8+2×4+2×4+3X4=55 s 2 4 0 4 ○ 7 ○3 4 ○4 8 3 ○ ○t （i） 可行流 f 4 ：v(f 4 )=11 s （2，5）（6，2）（2，4） ○ （1，7） （3，10） ○3 ○4 （a）费用、容量网络 ○2 ○t （4，10） （1，8） 图7-17 ⑺构造关于f 4的有向费用网络 W（f 4），如图7-17（j）所示。 由于在W（f 4）中无法找到从vs →vt 的最短路，所以 f 4 就是该网络的最 小费用最大流，流量v(f 4 )=11，其 分布情况如图7-17（i）所示。它对 应的总费用为： s 2 -2 6 ○ ○3 3 ○4 （j）费用网络W(f 4 ) 4 t -1 -1 -4 -3 -2 ○ ○ 2 b(f 4 )=4×3+1×7+1×8+2×4+2×4+3×4=55