教程：最大流-最小割定理课件.ppt

最大流最小割定理;一、割的有关概念和定量;1）、 顶点集合S={1，2，3}和T={4，5} 构成一个割。;1;1;◆ 如果一条弧的两个顶点分别属于顶点集S和T（一个顶点在S，另一个在T），那么这条弧称为割CUT（S,T）的一条割边。 ◆ 从S指向T的割边是正向割边； ◆ 从T指向S的割边是逆向割边。;如： 顶点集合S={1，3}，T={2，4，5}构成一个割。;◆ 割CUT（S,T）中所有正向割边的容量和称为割CUT（S,T）的容量。不同割的容量不同。;1;2、网络流与割的关系：;定理一： 如果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) 成立。;又因为： 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）的容量。;定量2： 在任何网络中，如果f是一个流，CUT（S,T）是一个割，且f的值等于割CUT（S,T）的容量，那么f是一个最大流，CUT（S,T）是一个最小割（容量最小的割）。;定量3：最大流最小割定量： 在任何的网络中，最大流的值等于最小割的容量。;结论1： 最大流时，最小割cut（S，T）中，正向割边的流量=容量，逆向割边的流量为0。否则还可以增广。;怎样求集合S？;水流管道的最大流量由最细的管子容量决定的;二、最大流最小割定量的应用;第1行有2 个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。 第1 行是实验编号；第2行是仪器编号；最后一行是净收益。;S;分析得出：;1;为定值：所有实验的收入;S;1;实验仪器和实验的输出：;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}：亏损的项目集合。 ;s