作者ybite (小犬)
看板Grad-ProbAsk
標題[理工] [Algo] 台大100-資工
時間Sat Feb 19 21:56:23 2011
還是趁著對題目有印象趕快發問...
這題不會，不過希望題目沒記錯
假若今天有一圖形如下
┌┬┬┬┬┬┬┬┬┬┐
├●┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼●┼┼┼┤
├┼┼●┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼●┼┼┤
├┼┼┼┼●┼┼┼┼┤
├●┼┼┼┼┼┼┼┼┤
└┴┴┴┴┴┴┴┴┴┘
在這個圖中，要判斷每個●點都有一條和走到圖形外圍的路徑，
且圖形中不會出現兩條路徑共用同一邊（只要證出是否即可）
舉例來說：
┌┬┬┬┬┬
┬┬┬┬┐
├●┼┼┼┼
┼┼┼┼┤
├┼┼┼┼┼
●┼┼┼┤
├┼┼●┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼
●┼┼┤
├┼┼┼┼
●┼┼┼┼┤
├●┼┼┼
┼┼┼┼┼┤
└┴┴┴┴
┴┴┴┴┴┘
真正的問題是：請把這個問題轉成一個Maxmium Flow問題...
-------
本來以為很簡單，但是Maxmium flow不是單向的嗎？ @@
還是要做兩次？ @@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.201.249
※ 編輯: ybite 來自: 220.131.201.249 (02/19 21:57)
1F：推 juan19283746:我是寫... S連到所有黑點 所有的外圍邊連到t 02/19 22:02
2F：→ juan19283746:然後其他點和編如同原圖 全部邊容量=1 02/19 22:02
3F：→ juan19283746:如果有流量>k的話 就可以ESCAPE 02/19 22:03
4F：→ juan19283746:應該不會差太多 可是我覺得應該有瑕疵 02/19 22:03
5F：→ juan19283746:就是方向的問題QQ 02/19 22:05
6F：→ ybite:我本來也想這樣寫，就是卡一個流量，所以沒寫下去... 02/19 22:17
7F：推 KiroKu:cormen的問題 流量=|v|就是有解 02/19 22:22
8F：推 cmuming:全部邊容量=1的狀況，等同允許一個點有兩個in兩個out 02/19 22:57
9F：→ ybite:理解，16分飛了qqqqqqqqqqqqqq 02/19 23:01
10F：推 nypgand1:請問"兩個in兩個out"是什麼意思阿? 可以舉一個轉過的圖嗎 02/19 23:43
11F：推 KiroKu:我覺得沒差吧 a->B c->D路徑有重疊的話 代表其實 a->D c->B 02/19 23:48
12F：推 cmuming:樓上如果發生"交叉"的話就不成立囉 02/20 23:05