最大流最小割定理课件

36、“不可能”这个字(法语是一个字)，只在愚人的字典中找得到。-拿破仑。37、不要生气要争气，不要看破要突破，不要嫉妒要欣赏，不要托延要积极，不要心动要行动。38、勤奋，机会，乐观是成功的三要素。(注意：传统观念认为勤奋和机会是成功的要素，但是经过统计学和成功人士的分析得出，乐观是成功的第三要素。39、没有不老的誓言，没有不变的承诺，踏上旅途，义无反顾。40、对时间的价值没有没有深切认识的人，决不会坚韧勤勉。最大流最小割定理12435642345412124352331s st t3 3）、）、顶点集合顶点集合S=S=1 1，3 3，5 5，T=2T=2，44不能不能构成一个割。构成一个割。？如果一条弧的两个顶点分别属于顶点集如果一条弧的两个顶点分别属于顶点集S S和和T T（一个顶点在（一个顶点在S S，另一个在，另一个在T T），那么），那么这条弧称为割这条弧称为割CUTCUT（S,TS,T）的一条）的一条割边割边。从从S S指向指向T T的割边是的割边是正向割边正向割边；从从T T指向指向S S的割边是的割边是逆向割边逆向割边。如：如：顶点集合顶点集合S=S=1 1，33，T=2T=2，4 4，5 5 构成一个割。构成一个割。12435642345412124352331s st t正向割边：正向割边：1 12;32;35 5逆向割边：逆向割边：2 23 3 割割CUTCUT（S,TS,T）中所有）中所有正向正向割边的容量和称为割割边的容量和称为割CUTCUT（S,TS,T）的容量。不同割的容量不同。）的容量。不同割的容量不同。12435642345412124352331s st t 容量为：容量为：3+4=73+4=712435642345412124352331s st t割的容量：割的容量：4+4=84+4=8割的正向流量：割的正向流量：4+2=64+2=6逆向割的流量：逆向割的流量：1 12 2、网络流与割的关系：、网络流与割的关系：12435642345412124352331s st t网络流量：网络流量：5 51 12 23 34 4割正逆161250350450割的流量割的流量定理一：定理一：如果如果f f是网络中的一个流，是网络中的一个流，CUTCUT（S,TS,T）是任意一个割，那）是任意一个割，那么么f f的值等于正向割边的流量与负向割边的流量之差。的值等于正向割边的流量与负向割边的流量之差。证明：设X和Y是网络中的两个顶点集合，用f（X,Y）表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X中，弧头在Y中：XY）的流量和.只需证明：f=f(S,T)-f(T,S)即可。如果如果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)成立。成立。下列结论成立：下列结论成立：根据网络流的特点：根据网络流的特点：如果如果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 又因为：又因为：f(S,ST)-f(ST,S)f(S,ST)-f(ST,S)=(f(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)定理得证定理得证推论推论1 1：如果如果f f是网络中的一个流，是网络中的一个流，CUTCUT（S,TS,T）是一个割，那）是一个割，那么么f f的值不超过割的值不超过割CUTCUT（S,TS,T）的容量。）的容量。f=f(S,T)-f(T,S)=f(S,T)=f=f(S,T)-f(T,S)=f(S,T)=割割CUTCUT（S,TS,T）的容量）的容量 推论推论2 2：网络中的最大流不超过任何割的容量网络中的最大流不超过任何割的容量 定量定量2 2：在任何网络中，如果在任何网络中，如果f f是一个流，是一个流，CUTCUT（S,TS,T）是一个割，）是一个割，且且f f的值等于割的值等于割CUTCUT（S,TS,T）的容量，那么）的容量，那么f f是一个最大流，是一个最大流，CUTCUT（S,TS,T）是一个最小割（容量最小的割）。）是一个最小割（容量最小的割）。令割令割CUTCUT（S,TS,T）的容量为）的容量为C C，所以流，所以流f f的流量也为的流量也为C C。假设另外的任意流假设另外的任意流f1f1，流量为，流量为c1c1，根据流量不超过割的，根据流量不超过割的容量，则容量，则c1=c,c1=c,c1=c,故，故，CUTCUT（S,TS,T）是最小割。）是最小割。证明：证明：定量定量3 3：最大流最小割定量：最大流最小割定量：在任何的网络中，最大流的值等在任何的网络中，最大流的值等于最小割的容量。于最小割的容量。12435642345212124354234522211122最大流：最大流：7 7S=1,2,3,T=4,5S=1,2,3,T=4,5Cut(S,T)Cut(S,T)是最小割，是最小割，容量容量结论结论1 1：最大流时，最小割最大流时，最小割cutcut（S S，T T）中，正向割边的流量）中，正向割边的流量=容量，容量，逆向割边的流量为逆向割边的流量为0 0。否则还可以增广。否则还可以增广。结论结论2 2：在最小割中在最小割中cutcut（S S，T T）中：）中：源点源点sSsS。如果如果iSiS，结点，结点j j满足：满足：有弧有弧,并且并且cI,jfI,jcI,jfI,j 或者有弧或者有弧并且并且fj,i0,fj,i0,那么那么jSjS。/否则不是最小割否则不是最小割 即从即从s s出发能找到的含有残留的点组成集合出发能找到的含有残留的点组成集合S S。其余的点。其余的点组成集合组成集合T T。怎样求集合怎样求集合S S？数组数组bibi记录增广路径上结点记录增广路径上结点i i的前驱结点。的前驱结点。初始值初始值b=-1b=-1，b1=0b1=0；假设；假设1 1是源点。是源点。如果如果bibi-1-1（有前驱，能从源点（有前驱，能从源点1 1找到的点），那么，找到的点），那么，iSiS。怎样求正向割边和逆向割边？怎样求正向割边和逆向割边？水流管道的最大流量由最细的管子容量决定的水流管道的最大流量由最细的管子容量决定的二、二、最大流最小割最大流最小割定量的应用定量的应用1 1、太空飞行计划问题、太空飞行计划问题【问题描述：】【问题描述：】W W 教授正在为国家航天中心计划一系列的太空飞行。每次教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合个可供选择的实验集合E=E1E=E1，E2E2，EmEm，和进行这些实验，和进行这些实验需要使用的全部仪器的集合需要使用的全部仪器的集合I=I1I=I1，I2I2，InIn。实验。实验EjEj需要用需要用到的仪器是到的仪器是I I的子集的子集Rj Rj。配置仪器。配置仪器IkIk的费用为的费用为ckck美元。实验美元。实验EjEj的赞助商已同意为该实验结果支付的赞助商已同意为该实验结果支付pjpj美元。美元。W W教授的任务是找出教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。指进行实验所获得的全部收入与配置仪器的全部费用的差额。对于给定的实验和仪器配置情况，编程找出净收益最大的对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。试验计划。第第1 1行有行有2 2 个正整数个正整数m m和和n n。m m是实验数，是实验数，n n是仪器数。接下来的是仪器数。接下来的m m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的一行的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 31717S ST TI1I1I2I2I3I3E1E1E2E25 56 67 710102525仪器仪器实验实验构造网络图构造网络图G G如下：如下：顶点个数：顶点个数：m+n+2m+n+2样例如右图：样例如右图：构造图时要重新编号构造图时要重新编号分析得出：分析得出：任意一种实验方案所做的实验以及所需的仪器以及任意一种实验方案所做的实验以及所需的仪器以及t t构成集构成集合合T T，剩下的不做的实验以及不需要的仪器和，剩下的不做的实验以及不需要的仪器和s s构成集合构成集合S S。T T和和S S正好对应与图的一个割。正好对应与图的一个割。S St tI1I1I2I2I3I3E1E1E2E25 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=17123123ts265394做实验做实验1 1：净收益：净收益：2-6=-42-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)为定值：所有实验的收入为定值：所有实验的收入要想净收益最大，那么割要想净收益最大，那么割CUT(S,T)CUT(S,T)的容的容量要最小：割的最小容量量要最小：割的最小容量=最大流最大流f f净收益净收益=所有实验收入所有实验收入-相应实验方案割的容量相应实验方案割的容量最大净收益最大净收益=所有实验收入所有实验收入-最大流最大流f fS St tI1I1I2I2I3I3E1E1E2E25 56 67 710102525仪器仪器实验实验最大净收益：最大净收益：（10+2510+25）-（5+6+75+6+7）=17=17123123ts265394最大净收益最大净收益：(2+5+9)(2+3+4)=16 最大流最大流 9=7做实验做实验 2和和3实验仪器和实验的输出：实验仪器和实验的输出：构造图时要重新编号构造图时要重新编号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,那么弧那么弧是一条割边是一条割边2 2、PlanPlan问题问题 （2000年国家集训队题目）【问题描述：】【问题描述：】某软件公司有某软件公司有n n个可选的程序项目，其中第个可选的程序项目，其中第i i个项目需要耗费资金个项目需要耗费资金aiai元，元，开发成功后可以获得的收益为开发成功后可以获得的收益为bibi元。元。当然，程序项目之间不是独立的：开发第当然，程序项目之间不是独立的：开发第i i个项目前，必须先开发出一个项目前，必须先开发出一些其他的项目，这些项目成为第些其他的项目，这些项目成为第i i个项目的个项目的“前驱项目前驱项目”。现在给出所有项目的现在给出所有项目的aiai和和bibi以及前驱项目。以及前驱项目。你的任务是：帮助该公司从这你的任务是：帮助该公司从这n n个程序项目中选择若干个进行开发，使个程序项目中选择若干个进行开发，使获得的总收益最大。获得的总收益最大。【输入：输入：】共共n+3n+3行。行。第一行：第一行：n n（1=n=2001=n=0:A=i|di=0:可以获得利润的项目集合。可以获得利润的项目集合。B=i|di0B=i|di0：亏损的项目集合。：亏损的项目集合。构造网络图：构造网络图：G=G=（V V，E E，C C）。）。1 1、两类顶点：、两类顶点：N+2N+2个点：源点个点：源点s s个汇点个汇点t t，第，第i i个项目点个项目点vivi。2 2、三种弧：、三种弧：如果如果iAiA，存在弧，存在弧,容量为容量为didi。如果如果iBiB，存在弧，存在弧,容量法容量法|di|di|。如果如果i i个前驱项目为个前驱项目为j j，存在弧，存在弧，容量为，容量为+。s st t1 12 23 34 45 56 67 78 8构造割构造割cutcut（S S，T T），如果），如果iTiT，则，则i i的前驱的前驱jTjT。割对应一种实验方案。割对应一种实验方案。求出最大流求出最大流f f。最大收益：最大收益：A AB BS ST T6、最大的骄傲于最大的自卑都表示心灵的最软弱无力。、最大的骄傲于最大的自卑都表示心灵的最软弱无力。斯宾诺莎斯宾诺莎7、自知之明是最难得的知识。、自知之明是最难得的知识。西班牙西班牙8、勇气通往天堂，怯懦通往地狱。、勇气通往天堂，怯懦通往地狱。塞内加塞内加9、有时候读书是一种巧妙地避开思考的方法。、有时候读书是一种巧妙地避开思考的方法。赫尔普斯赫尔普斯10、阅读一切好书如同和过去最杰出的人谈话。、阅读一切好书如同和过去最杰出的人谈话。笛卡儿笛卡儿 Thank you拯畏怖汾关炉烹霉躲渠早膘岸缅兰辆坐蔬光膊列板哮瞥疹傻俘源拯割宜跟三叉神经痛-治疗三叉神经痛-治疗