36、“不可能”這個字(法語是一個字)，只在愚人的字典中找得到。--拿破侖。37、不要生氣要爭氣，不要看破要突破，不要嫉妒要欣賞，不要托延要積極，不要心動要行動。38、勤奮，機會，樂觀是成功的三要素。(注意：傳統觀念認為勤奮和機會是成功的要素，但是經過統計學和成功人士的分析得出，樂觀是成功的第三要素。39、沒有不老的誓言，沒有不變的承諾，踏上旅途，義無反顧。40、對時間的價值沒有沒有深切認識的人，決不會堅韌勤勉。最大流最小割定理最大流最小割定理36、“不可能”這個字(法語是一個字)，只在愚人的字典中找得到。--拿破侖。37、不要生氣要爭氣，不要看破要突破，不要嫉妒要欣賞，不要托延要積極，不要心動要行動。38、勤奮，機會，樂觀是成功的三要素。(注意：傳統觀念認為勤奮和機會是成功的要素，但是經過統計學和成功人士的分析得出，樂觀是成功的第三要素。39、沒有不老的誓言，沒有不變的承諾，踏上旅途，義無反顧。40、對時間的價值沒有沒有深切認識的人，決不會堅韌勤勉。最大流最小割定理最大流最小割定理網絡流之二一、割的有關概念和定量1、割的定義：割（CUT）是網絡中頂點的一個劃分，它把網絡中的所有頂點劃分成兩個頂點集合S和T，其中源點s∈S，匯點t∈T。記為CUT（S,T）。如右圖：源點：s=1；匯點：t=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正向割邊：12;35逆向割邊：23◆割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中：XY）的流量和.只需證明：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)為定值：所有實驗的收入要想凈收益最大，那么割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|di<0}：虧損的項目集合。構造網絡圖：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。割對應一種實驗方案。求出