推 a613204:看起來跟我的作法一樣,不過應該不一定要從最下面開始看吧? 01/06 19:54
→ justbelieve:不一定阿,我只是想說記一個固定的方法而已 01/06 20:09
推 qqoil:我習慣從上面來 ㄎㄎ 01/09 15:54
剛好上週上課有講到
我記的老師的講法是說
假設以下面這個圖來看(出處100彰師)
b----9---e
/ \ / \
8 / \3 /2 \4
/ \ / \
a/___3___\d___6___z
\ / \ /
9\ 4/ \2 /3
\ / \ /
\/___3___\/
c f
a為起點,z為終點
先從最下面的路徑來看(記得老師是說都先從最下面開始看)
發現最小的管子(邊)容量是3
所以下面的流量依序改成(9,3),(3,3),(3,3)
(c,f)和(f,z)因為已經滿了所以不能走了
(a,c)=(9,3)還可以通過6,還沒滿繼續找可以走的管子
走(c,d),(d,f)因為(f,z)不能走所以邊改成(2,0),然後走(d,z)
因為此時最小的管子容量是4,所以將(a,c),(c,d)(d,z)依序改成(9,7),(4,4),(6,4)
此時,(a,c)已經沒有路可以走了,所以開始往上一條管子(a,d)去走,
依照前面的方法去走
最後的流量圖為:
9,2
b--------e
/ \ / \
8,3 3,1 2,2 4,4
/ \ / \
a/__3,3__\d__6,6__z
\ / \ /
9,7 4,4 2,0 3,3
\ / \ /
\/__3,3__\/
c f
找min cut是去看圖的所有滿的管子,能夠將圖切成2邊的
其中流進cut的必須是滿的
所以像(f,z),(d,z),(d,e)雖然是滿的,但(b,e)沒滿,所以不行
我們可以找到(e,z),(d,z),(f,z)是滿的,且恰能將圖切成2邊
cut的左邊的點屬於P = {a,b,c,d,e,f},右邊屬於非P = {z}
min cut(P,非P) = max flow = 13
以上如果有錯的地方麻煩請各位高手說一下
好讓小弟趕快把錯的觀念修正
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.105.52.42