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

最大流最小割定理网络流之二一、割的有关概念和定量1、割的定义：割（CUT）是网络中顶点的一个划分，它把网络中的所有顶点划分成两个顶点集合S和T，其中源点s∈S，汇点t∈T。记为CUT（S,T）。如右图：源点：s=1；汇点：t=5。框外是容量，框内是流量12435642345412124352331st1）、顶点集合S={1，2，3}和T={4，5}构成一个割。12435642345412124352331st12435642345412124352331st2）、顶点集合S={1，3}，T={2，4，5}构成一个割。12435642345412124352331st3）、顶点集合S={1，3，5}，T={2，4}不能构成一个割。？◆如果一条弧的两个顶点分别属于顶点集S和T（一个顶点在S，另一个在T），那么这条弧称为割CUT（S,T）的一条割边。◆从S指向T的割边是正向割边；◆从T指向S的割边是逆向割边。如：顶点集合S={1，3}，T={2，4，5}构成一个割。12435642345412124352331st正向割边：12;35逆向割边：23◆割CUT（S,T）中所有正向割边的容量和称为割CUT（S,T）的容量。不同割的容量不同。12435642345412124352331st容量为：3+4=712435642345412124352331st割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：12、网络流与割的关系：12435642345412124352331st网络流量：51234割正逆161250350450割的流量定理一：如果f是网络中的一个流，CUT（S,T）是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。证明：设X和Y是网络中的两个顶点集合，用f（X,Y）表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X中，弧头在Y中：XY）的流量和.只需证明：f=f(S,T)-f(T,S)即可。如果X∩Y=，那么：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2)f((X1∪X2),Y)=f(X1,Y)+f(X2,Y)成立。下列结论成立：根据网络流的特点：如果V既不是源点也不是汇点，那么：f({V},S∪T)-f(S∪T,{V})=0;任何一个点，流入的与流出的量相等。如果V是源，那么：f({V},S∪T)-f(S∪T,{V})=f对于S中的所有点V都有上述关系式，相加得到：f(S,S∪T)-f(S∪T,S)=f又因为：f(S,S∪T)-f(S∪T,S)=(f(S,S)+f(S,T))-(f(S,S)+f(T,S))=f(S,T)-f(T,S)所以：f=f(S,T)-f(T,S)定理得证推论1：如果f是网络中的一个流，CUT（S,T）是一个割，那么f的值不超过割CUT（S,T）的容量。f=f(S,T)-f(T,S)=f(S,T)=割CUT（S,T）的容量推论2：网络中的最大流不超过任何割的容量定量2：在任何网络中，如果f是一个流，CUT（S,T）是一个割，且f的值等于割CUT（S,T）的容量，那么f是一个最大流，CUT（S,T）是一个最小割（容量最小的割）。令割CUT（S,T）的容量为C，所以流f的流量也为C。假设另外的任意流f1，流量为c1，根据流量不超过割的容量，则c1=c,所以f是最大流。假设另外的任意割CUT（S1,T1），容量为c1，根据流量不超过割的容量，所以有c1=c,故，CUT（S,T）是最小割。证明：定量3：最大流最小割定量：在任何的网络中，最大流的值等于最小割的容量。12435642345212124354234522211122最大流：7S={1,2,3},T={4,5}Cut(S,T)是最小割，容量＝３＋４＝７结论1：最大流时，最小割cut（S，T）中，正向割边的流量=容量，逆向割边的流量为0。否则还可以增广。结论2：在最小割中cut（S，T）中：①源点s∈S。②如果i∈S，结点j满足：有弧i,j,并且c[I,j]f[I,j]或者有弧j,i并且f[j,i]0,那么j∈S。//否则不是最小割即从s出发能找到的含有残留的点组成集合S。其余的点组成集合T。怎样求集合S？数组b[i]记录增广路径上结点i的前驱结点。初始值b[]=-1，b[1]=0；假设1是源点。如果b[i]〉-1（有前驱，能从源点1找到的点），那么，i∈S。怎样求正向割边和逆向割边？水流管道的最大流量由最细的管子容量决定的二、最大流最小割定量的应用1、太空飞行计划问题【问题描述：】W教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集Rj。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。第1行有2个正整数m和n。m是实验数，n是仪器数。接下来的m行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。第1行是实验编号；第2行是仪器编号；最后一行是净收益。【输入：】【输出:】【样例输入:】2310122523567【样例输出:】1212317STI1I2I3E1E25671025仪器实验∞∞∞∞构造网络图G如下：顶点个数：m+n+2样例如右图：构造图时要重新编号分析得出：任意一种实验方案所做的实验以及所需的仪器以及t构成集合T，剩下的不做的实验以及不需要的仪器和s构成集合S。T和S正好对应与图的一个割。StI1I2I3E1E25671025仪器实验∞∞∞∞如做实验E2：需要仪器I2和I3，与t组成集合T。S与不做的实验E1和没用的仪器I1组成集合S。构成割：CUT(S,T)净收益：E2:25-（6+7）=12同理:E1：10-（5+6）=-1E1+E2：（10+25）-（5+6+7）=17123123ts265394做实验1：净收益：2-6=-4做实验1，2：净收益：（2+5）-（6+3）=-2做实验2，3：净收益：（5+9）-（3+4）=7=(2+5+9)-(5+9)-6=(2+5+9)-(5+9+6)=(2+5+9)-9-(6+3)=(2+5+9)-(9+6+3)=(2+5+9)-2-(3+4)=(2+5+9)-(2+3+4)111()(,)jkjkjkmjkjjkETITjESITmmjjkjjESITjpCppCppCpcutST1mjjp为定值：所有实验的收入要想净收益最大，那么割CUT(S,T)的容量要最小：割的最小容量=最大流f净收益=所有实验收入-相应实验方案割的容量最大净收益=所有实验收入-最大流fStI1I2I3E1E25671025仪器实验∞∞∞∞最大净收益：（10+25）-（5+6+7）=17123123ts265394最大净收益：(2+5+9)–(2+3+4)=16–最大流9=7做实验2和3实验仪器和实验的输出：构造图时要重新编号123123ts265394仪器：1-3中b[i]=-1的点。实验：4-6中b[j]=-1的点。割边：如果存在弧i,j，满足：i∈S,b[i]=0,j∈T,b[j]=-1,那么弧i,j是一条割边2、Plan问题（2000年国家集训队题目）【问题描述：】某软件公司有n个可选的程序项目，其中第i个项目需要耗费资金ai元，开发成功后可以获得的收益为bi元。当然，程序项目之间不是独立的：开发第i个项目前，必须先开发出一些其他的项目，这些项目成为第i个项目的“前驱项目”。现在给出所有项目的ai和bi以及前驱项目。你的任务是：帮助该公司从这n个程序项目中选择若干个进行开发，使获得的总收益最大。【输入：】共n+3行。第一行：n（1=n=200）.第二行有n个正整数：a1，a2，。。。，an。第三行有n个正整数：b1，b2，。。。，bn。以下n行，第i行每行包含若干个正整数：ri，k1，k2，。。。，kri。第一个数ri表示第i个项目有ri个前驱项目，ri，k1，k2，。。。，kri表示i个ri个前驱项目。【输出：】一个整数max，表示最大收益。分析：令di=bi-ai，净收益。A={i|di=0}:可以获得利润的项目集合。B={i|di0}：亏损的项目集合。构造网络图：G=（V，E，C）。1、两类顶点：N+2个点：源点s个汇点t，第i个项目点vi。2、三种弧：如果i∈A，存在弧i,t,容量为di。如果i∈B，存在弧s,i,容量法|di|。如果i个前驱项目为j，存在弧j,i，容量为+∞。st12345678构造割cut（S，T），如果i∈T，则i的前驱j∈T。割对应一种实验方案。求出最大流f。最大收益：iAdifABST