教程：最大流-最小割定理

1、a1最大流最小割定理最大流最小割定理网络流之二网络流之二a2一、割的有关概念和定量一、割的有关概念和定量1、割的定义：、割的定义：割割CUTCUT是网络中顶点的一个划分，它把网络中的所有顶点划分成是网络中顶点的一个划分，它把网络中的所有顶点划分成两个顶点集合两个顶点集合S S和和T T，其中源点，其中源点sSsS，汇点，汇点tTtT。记为。记为CUTCUTS,TS,T。如右图：源点：如右图：源点：s=1s=1；汇点：；汇点：t=5t=5。框外是容量，框内是流量框外是容量，框内是流量12435642345412124352331s st ta31 1、顶点集合顶点集合S=1S=1，2 2，33和

2、和T=4T=4，55构成一个割。构成一个割。12435642345412124352331s st ta412435642345412124352331s st t2 2、顶点集合顶点集合S=1S=1，33，T=2T=2，4 4，55构成一个割。构成一个割。a512435642345412124352331s st t3 3、顶点集合顶点集合S=1S=1，3 3，55，T=2T=2，44不能不能构成一个割。构成一个割。？a6 如果一条弧的两个顶点分别属于顶点集如果一条弧的两个顶点分别属于顶点集S S和和T T一个顶点在一个顶点在S S，另一个在，另一个在T T，那么，那么这条弧称为割这条弧称为

3、割CUTCUTS,TS,T的一条割边。的一条割边。 从从S S指向指向T T的割边是正向割边；的割边是正向割边； 从从T T指向指向S S的割边是逆向割边。的割边是逆向割边。a7如：如：顶点集合顶点集合S=S=1 1，33，T=2T=2，4 4，5 5 构成一个割。构成一个割。12435642345412124352331s st t正向割边：正向割边：1 12;32;35 5逆向割边：逆向割边：2 23 3a8 割割CUTCUTS,TS,T中所有正向割边的容量和称为割中所有正向割边的容量和称为割CUTCUTS,TS,T的容量。不同割的容量不同。的容量。不同割的容量不同。12435642345

4、412124352331s st t 容量为：容量为：3+4=73+4=7a912435642345412124352331s st t割的容量：割的容量：4+4=84+4=8割的正向流量：割的正向流量：4+2=64+2=6逆向割的流量：逆向割的流量：1 1a102 2、网络流与割的关系：、网络流与割的关系：12435642345412124352331s st t网络流量：网络流量：5 51 12 23 34 4割正逆161250350450割的流量割的流量a11定理一：定理一： 如果如果f f是网络中的一个流，是网络中的一个流，CUTCUTS,TS,T是任意一个割，那是任意一个割，那么么f

5、 f的值等于正向割边的流量与负向割边的流量之差。的值等于正向割边的流量与负向割边的流量之差。证明： 设X和Y是网络中的两个顶点集合，用fX,Y表示从X中的一个顶点指向Y的一个顶点的所有弧弧尾在X中，弧头在Y中：XY的流量和.只需证明：f=f(S,T)-f(T,S) 即可。a12如果如果XY= XY= ，那么：，那么：f(X,(Y1Y2)=f(X,Y1)+f(X,Y2) f(X,(Y1Y2)=f(X,Y1)+f(X,Y2) f(X1X2),Y)=f(X1,Y)+f(X2,Y) f(X1X2),Y)=f(X1,Y)+f(X2,Y) 成立。成立。以下结论成立：以下结论成立：根据网络流的特点：根据网络

6、流的特点：如果如果V V既不是源点也不是汇点，那么：既不是源点也不是汇点，那么： f(V,ST)-f(ST,V)=0;f(V,ST)-f(ST,V)=0; 任何一个点，流入的与流出的量相等。任何一个点，流入的与流出的量相等。如果如果V V是源，那么：是源，那么： f(V,ST)-f(ST,V)=f f(V,ST)-f(ST,V)=f 对于对于S S中的所有点中的所有点V V都有上述关系式，相加得到：都有上述关系式，相加得到： f(S,ST)-f(ST,S)=f f(S,ST)-f(ST,S)=f a13又因为：又因为： f(S,ST)-f (ST,S)f(S,ST)-f (ST,S) = (f

7、(S,S)+f (S,T)-(f(S,S) +f (T,S) = (f(S,S)+f (S,T)-(f(S,S) +f (T,S) = f(S,T)- f(T,S) = f(S,T)- f(T,S)所以：所以：f= f(S,T)- f(T,S) f= f(S,T)- f(T,S) 定理得证定理得证a14推论推论1 1： 如果如果f f是网络中的一个流，是网络中的一个流，CUTCUTS,TS,T是一个割，那是一个割，那么么f f的值不超过割的值不超过割CUTCUTS,TS,T的容量。的容量。f= f(S,T)- f(T,S)=f(S,T)=f= f(S,T)- f(T,S)=f(S,T)=割割C

8、UTCUTS,TS,T的容量的容量 推论推论2 2： 网络中的最大流不超过任何割的容量网络中的最大流不超过任何割的容量 a15定量定量2 2： 在任何网络中，如果在任何网络中，如果f f是一个流，是一个流，CUTCUTS,TS,T是一个割，是一个割，且且f f的值等于割的值等于割CUTCUTS,TS,T的容量，那么的容量，那么f f是一个最大流，是一个最大流，CUTCUTS,TS,T是一个最小割容量最小的割。是一个最小割容量最小的割。 令割令割CUTCUTS,TS,T的容量为的容量为C C，所以流，所以流f f的流量也为的流量也为C C。 假设另外的任意流假设另外的任意流f1f1，流量为，流量

9、为c1c1，根据流量不超过割的，根据流量不超过割的容量，那么容量，那么c1=c,c1=c,c1=c,故，故，CUTCUTS,TS,T是最小割。是最小割。证明：证明：a16定量定量3 3：最大流最小割定量：最大流最小割定量： 在任何的网络中，最大流的值等在任何的网络中，最大流的值等于最小割的容量。于最小割的容量。12435642345212124354234522211122最大流：最大流：7 7S=1,2,3,T=4,5S=1,2,3,T=4,5Cut(S,T)Cut(S,T)是最小割，是最小割，容量容量a17结论结论1 1： 最大流时，最小割最大流时，最小割cutcutS S，T T中，正向

10、割边的流量中，正向割边的流量= =容量，容量，逆向割边的流量为逆向割边的流量为0 0。否那么还可以增广。否那么还可以增广。结论结论2 2： 在最小割中在最小割中cutcutS S，T T中：中： 源点源点sSsS。 如果如果iSiS，结点，结点j j满足：满足： 有弧有弧,并且并且cI,jfI,jcI,jfI,j 或者有弧或者有弧并且并且fj,i0,fj,i0, 那么那么jSjS。/否那么不是最小割否那么不是最小割 即从即从s s出发能找到的含有残留的点组成集合出发能找到的含有残留的点组成集合S S。其余的点。其余的点组成集合组成集合T T。a18怎样求集合怎样求集合S S？数组数组bibi记

11、录增广路径上结点记录增广路径上结点i i的前驱结点。的前驱结点。初始值初始值b= -1b= -1，b1=0b1=0；假设；假设1 1是源点。是源点。如果如果bibi-1-1有前驱，能从源点有前驱，能从源点1 1找到的点，那么，找到的点，那么，iSiS。怎样求正向割边和逆向割边？怎样求正向割边和逆向割边？a19水流管道的最大流量由最细的管子容量决定的水流管道的最大流量由最细的管子容量决定的a20二、二、最大流最小割最大流最小割定量的应用定量的应用1 1、太空飞行方案问题、太空飞行方案问题【问题描述：】【问题描述：】 W W 教授正在为国家航天中心方案一系列的太空飞教授正在为国家航天中心方案一系列

12、的太空飞行。每次太空飞行可进行一系列商业性实验而获取利行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合润。现已确定了一个可供选择的实验集合E=E1E=E1，E2E2，EmEm，和进行这些实验需要使用的全部仪器的，和进行这些实验需要使用的全部仪器的集合集合I=I1I=I1，I2I2，InIn。实验。实验EjEj需要用到的仪器是需要用到的仪器是I I的的子集子集Rj Rj 。配置仪器。配置仪器IkIk的费用为的费用为ckck美元。实验美元。实验EjEj的赞助的赞助商已同意为该实验结果支付商已同意为该实验结果支付pjpj美元。美元。W W教授的任务是找教授的任务是找

13、出一个有效算法，确定在一次太空飞行中要进行哪些出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。配置仪器的全部费用的差额。 对于给定的实验和仪器配置情况，编程找出净收对于给定的实验和仪器配置情况，编程找出净收益最大的试验方案。益最大的试验方案。a21第第1 1行有行有2 2 个正整数个正整数m m和和n n。m m是实验数，是实验数，n n是仪器数。接下来的是仪器数。接下来的m m 行，每行

14、是一个实验的有关数据。第一个数赞助商同意支付该行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的假设干仪器的编号。最实验的费用；接着是该实验需要用到的假设干仪器的编号。最后一行的后一行的n n个数是配置每个仪器的费用。个数是配置每个仪器的费用。第第1 1 行是实验编号；第行是实验编号；第2 2行是仪器编号；最后一行是净收益。行是仪器编号；最后一行是净收益。【输入：】【输入：】【输出【输出: :】【样例输入样例输入: :】2 32 310 1 210 1 225 2 325 2 35 6 75 6 7【样例输出样例输出: :】1 21 21 2 31 2 3

15、1717a22S ST TI1I1I2I2I3I3E1E1E2E25 56 67 710102525仪器仪器实验实验构造网络图构造网络图G G如下：如下：顶点个数：顶点个数：m+n+2m+n+2样例如右图：样例如右图：构造图时要重新编号构造图时要重新编号a23分析得出：分析得出：任意一种实验方案所做的实验以及所需的仪器以及任意一种实验方案所做的实验以及所需的仪器以及t t构成集构成集合合T T，剩下的不做的实验以及不需要的仪器和，剩下的不做的实验以及不需要的仪器和s s构成集合构成集合S S。T T和和S S正好对应与图的一个割。正好对应与图的一个割。S St tI1I1I2I2I3I3E1E

16、1E2E25 56 67 710102525仪器仪器实验实验如做实验如做实验E2E2：需要仪器：需要仪器I2I2和和I3I3，与，与t t组成集合组成集合T T。S S与不做的实验与不做的实验E1E1和没用的和没用的仪器仪器I1I1组成集合组成集合S S。构成割：构成割：CUT(S,T)CUT(S,T)净收益：净收益： E2:25-E2:25-6+76+7=12=12同理同理 : :E1E1：10-10-5+65+6= -1= -1E1+E2E1+E2：10+2510+25- -5+6+75+6+7=17=17a24123123ts265394做实验做实验1 1：净收益：净收益：2-6=-42

17、-6=-4做实验做实验1 1，2 2：净收益：净收益：2+52+5- -6+36+3=-2=-2做实验做实验2 2，3 3：净收益：净收益：5+95+9- -3+43+4=7=7=(2+5+9)-(5+9)-6=(2+5+9)-(=(2+5+9)-(5+9)-6=(2+5+9)-(5+9+65+9+6) )=(2+5+9)-9-(6+3)=(2+5+9)-(=(2+5+9)-9-(6+3)=(2+5+9)-(9+6+39+6+3) )=(2+5+9)-2-(3+4)=(2+5+9)-(=(2+5+9)-2-(3+4)=(2+5+9)-(2+3+42+3+4) )a25111()( , )jkj

18、kjkmjkjjkETITjESITmmjjkjjESITjpCppCppCpcut S T1mjjp为定值：所有实验的收入为定值：所有实验的收入要想净收益最大，那么割要想净收益最大，那么割CUT(S,T)CUT(S,T)的容的容量要最小：割的最小容量量要最小：割的最小容量= =最大流最大流f f净收益净收益= =所有实验收入所有实验收入- -相应实验方案割的容量相应实验方案割的容量最大净收益最大净收益= =所有实验收入所有实验收入- -最大流最大流f fa26S St tI1I1I2I2I3I3E1E1E2E25 56 67 710102525仪器仪器实验实验最大净收益：最大净收益： 10+

19、2510+25- -5+6+75+6+7=17=17a27123123ts265394最大净收益最大净收益：(2+5+9) ( 2+3+4 )= 16 最大流最大流 9 = 7做实验做实验 2和和3a28实验仪器和实验的输出：实验仪器和实验的输出：构造图时要重新编号构造图时要重新编号123123ts265394仪器：仪器：1-31-3中中bi=-1bi=-1的点。的点。实验：实验：4-64-6中中bj=-1bj=-1的点。的点。割边：如果存在弧割边：如果存在弧，满足：满足：iS,bi=0,iS,bi=0, jT,bj= -1, jT,bj= -1,那么弧那么弧是一条割边是一条割边a292 2、PlanPlan问题问题 20002000年国家集训队题目年国家集训队题目【问题描述：】【问题描述：】 某软件公司有某软件公司有n n个可选的程序工程，其中第个可选的程序工程，其中第i i个工程需要消耗资金个工程需要消耗资金aiai元，开发成功后可以获元，开发成功后可以获得的收益为得的收益为bibi元。元。 当然，程序工程之间不是独立的：开发第当然，程序工程之间不是独立的：开发第i i个工程前，必