§94最小费用流问题 概念 1.费用网络:对网络N=(V,x,y,A,C),给其每条弧(,v)赋以一个非负实数(权)v(u,v),称 为弧(l4,v)的单位费用。这种每条弧都带有单位费用的网络,称为费用网络,记为 N=(V,x,y,A,C,w)或N=(,A,C,w),其中w为费用函数 2.费用网络N=(V,x,y,A,C,v)中流∫的费用 n()=∑[van)·f(u) 3.最小费用流问题:对于网络N=(V,x,y,A,C,v)和一个给定的数v0≥0,求N中流值为v 且费用最小的可行流 二、求最小费用流的负费用圈算法 定义941费用网络的增量网络: 设∫是网络N=(,x,y,AC,w)上的一个可行流,N关于∫的增量网络为 N=(V,x,y,A(O),C’,v’) 其中A(f),C’,及w’如下: (1)若(u,v)∈A且f(l,y)<C(u,v),则(u,v)∈A(f),且 C'(a,v)=C(u,v)-f(l,v),w(u,)=v(,v) (2)若(u,v)∈A且f(ul,v)>0,则(v,u)∈A(O),且 C'(v,u)=f(u,v),w(v,n)=-(l,y); 例 2、(3.4) 22) (14) 0.(1,1) 0,(2,5) (1,1) 网络N及其一个可行流f,每条弧 增量网络M∥,每条弧上的二元 上的三元数组分别表示f(c,w) 数组分别表示(c,w) 定义942设∫是N的一个可行流,∫'是N(f)的一个可行流,则可得N中一个新的可行流f:对 l,v)∈A f(u, v)=f(u,v)+f(u,v)-f'(v, u) 称广是∫在∫上的叠加,记为:f+f'。 引理941设∫是N的可行流,∫是N(的一个可行流,则 Val(f+f)=val f+val, w(f+f)=w(f)+w(f)§9.4 最小费用流问题 一、概念 1. 费用网络：对网络 N V x y AC = (,,,, ) ，给其每条弧(,) u v 赋以一个非负实数(权)wuv (,) ，称 为弧(,) u v 的单位费用。这种每条弧都带有单位费用的网络，称为费用网络，记为 N V x y AC w = (,,,, , ) 或 N V AC w = (,, , ) ，其中 w 为费用函数。 2. 费用网络 N V x y AC w = (,,,, , ) 中流 f 的费用： (,) ( ) [ ( , ) ( , )] uv A w f wuv f uv ∈ = ⋅ ∑ 。 3. 最小费用流问题：对于网络 N V x y AC w = (,,,, , ) 和一个给定的数 0 v ≥ 0，求 N 中流值为 0 v 且费用最小的可行流。 二、求最小费用流的负费用圈算法 定义 9.4.1 费用网络的增量网络： 设 f 是网络 N V x y AC w = (,,,, , ) 上的一个可行流，N 关于 f 的增量网络为 N VxyAf C w = ( , , , ( ), , ) ′ ′ ， 其中 Af C w ( ), ,′ ′ 及 如下： (1) 若（uv A , ) ∈ 且 f (,) (,) uv Cuv < ，则(,) ( ) uv A f ∈ ，且 C uv Cuv f uv w uv wuv ′ ′ ( , ) ( , ) ( , ), ( , ) ( , ); = − = (2) 若（uv A , ) ∈ 且 f uv (,) 0 > ，则(, ) ( ) vu A f ∈ ，且 C vu f uv w vu wuv ′ ′ ( , ) ( , ), ( , ) ( , ); = =− 例： 定义 9.4.2 设 f 是 N 的一个可行流， f ′是 N f ( ) 的一个可行流，则可得 N 中一个新的可行流 * f ：对 ∀ ∈ (,) uv A， * f (, ) (,) (, ) (, ) uv f uv f uv f vu =+ − ′ ′ 称 * f 是 f ′在 f 上的叠加，记为： f + f ′。 引理 9.4.1 设 f 是 N 的可行流， f ′是 N f ( ) 的一个可行流，则 () , ( ) ( ) ( ). Val f f Val f Val f wf f wf w f ′ = + ′ ′ = + ′ ′ + +   网络 N 及其一个可行流 f ，每条弧 上的三元数组分别表示 f, (c, w)。 2,(2,2) 1,(3,3) 2,(3,4) 0,(1,1) 2,(3,1) 0,(2,5) 1,(3,2) x y 增量网络 N(f) ，每条弧上的二元 数组分别表示 (c′, w′ )。 (2,−2) (2,3) (1,4) (1,1) (1,1) (2,5) (2,2) x y (1,−3) (1,−2) (2,−1) (2,−4)