最大流最小割定理一、割的有关概念和定量1）、顶点集合S={1，2，3}和T={4，5}构成一个割。11◆如果一条弧的两个顶点分别属于顶点集S和T〔一个顶点在S，另一个在T），那么这条弧称为割CUT〔S,T〕的一条割边。◆从S指向T的割边是正向割边；◆从T指向S的割边是逆向割边。如：顶点集合S={1，3}，T={2，4，5}构成一个割。◆割CUT〔S,T〕中所有正向割边的容量和称为割CUT〔S,T〕的容量。不同割的容量不同。12、网络流与割的关系：定理一：如果f是网络中的一个流，CUT〔S,T〕是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。如果X∩Y=，那么：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2)f((X1∪X2),Y)=f(X1,Y)+f(X2,Y)成立。第三行有n个正整数：b1，b2，。A={i|di>=0}:可以获得利润的项目集合。f((X1∪X2),Y)=f(X1,Y)+f(X2,Y)成立。对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。顶点集合S={1，2，3}和T={4，5}，kri表示i个ri个前驱项目。构造网络图：G=（V，E，C）。构造网络图：G=（V，E，C）。Cut(S,T)是最小割，容量＝３＋４＝７如果V既不是源点也不是汇点，那么：那么弧<i,j>是一条割边m是实验数，n是仪器数。现在给出所有项目的ai和bi以及前驱项目。二、最大流最小割定量的应用现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。推论1：如果f是网络中的一个流，CUT〔S,T〕是一个割，那么f的值不超过割CUT〔S,T〕的容量。定量2：在任何网络中，如果f是一个流，CUT〔S,T〕是一个割，且f的值等于割CUT〔S,T〕的容量，那么f是一个最大流，CUT〔S,T〕是一个最小割〔容量最小的割）。S={1,2,3},T={4,5}如果f是网络中的一个流，CUT〔S,T〕是一个割，那么f的值不超过割CUT〔S,T〕的容量。一个整数max，表示最大收益。如果i个前驱项目为j，存在弧<j,i>，容量为+∞。如果i∈B，存在弧<s,i>,容量法|di|。W教授正在为国家航天中心计划一系列的太空飞行。◆从S指向T的割边是正向割边；第1行有2个正整数m和n。配置仪器Ik的费用为ck美元。第三行有n个正整数：b1，b2，。如果i∈B，存在弧<s,i>,容量法|di|。2、Plan问题（2000年国家集训队题目）=(2+5+9)-(5+9)-6=(2+5+9)-(5+9+6)在最小割中cut〔S，T〕中：所以：f=f(S,T)-f(T,S)定理得证构成割：CUT(S,T)W教授正在为国家航天中心计划一系列的太空飞行。结论1：最大流时，最小割cut〔S，T〕中，正向割边的流量=容量，逆向割边的流量为0。否则还可以增广。怎样求集合S？水流管道的最大流量由最细的管子容量决定的二、最大流最小割定量的应用第1行有2个正整数m和n。m是实验数，n是仪器数。接下来的m行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。第1行是实验编号；第2行是仪器编号；最后一行是净收益。S分析得出：1为定值：所有实验的收入S1实验仪器和实验的输出：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|di<0}：亏损的项目集合。s谢谢