Posted on 2012-05-06 02:55
lenohoo 閱讀(119)
評論(0) 編輯 收藏 引用
將s看成源點,t看成匯點,有結論:源點到匯點的最小點割集的大小等于圖中最多的點不相交路徑數目
做法:將每個點拆成兩個點u和u',之間連容量為1的邊,原來從u到v的邊,變成從u'到v的邊,邊容量都是無窮大,新源點為s',新匯點還是t
這樣,就將點不相交問題轉化成邊不相交問題,每條點不相交路徑和一條邊不相交路徑一一對應
當有流值v時,意味著有v條邊不相交路徑(容量為1的限制),任意割的容量p>=v,每條邊不相交路徑中必有一條邊是割邊,當割是最小割
時,p=v,v為最大流,這時,最小點割集的大小就是最小邊割集的大小也就是最大流
于是,當源點和匯點不直接相連的情況下,我們就得到了我們的第一個答案
但是題目要求很高,需要輸出分數最小的點割集,即按字典序排序最小,我們可以貪心地從最小標號的頂點到最大標號的頂點一次枚舉,每次刪
除邊i和i',如果新的最大流比原來的最大流小,說明該點在最小點割集中,否則,恢復邊i和i'(不然可能將原來不是割點的點變成割點)