› 看板 Grad-ProbAsk 關於我們 聯絡資訊
作者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)
推 juan19283746:我是寫... S連到所有黑點 所有的外圍邊連到t 02/19 22:02
→ juan19283746:然後其他點和編如同原圖 全部邊容量=1 02/19 22:02
→ juan19283746:如果有流量>k的話 就可以ESCAPE 02/19 22:03
→ juan19283746:應該不會差太多 可是我覺得應該有瑕疵 02/19 22:03
→ juan19283746:就是方向的問題QQ 02/19 22:05
→ ybite:我本來也想這樣寫，就是卡一個流量，所以沒寫下去... 02/19 22:17
推 KiroKu:cormen的問題 流量=|v|就是有解 02/19 22:22
推 cmuming:全部邊容量=1的狀況，等同允許一個點有兩個in兩個out 02/19 22:57
→ ybite:理解，16分飛了qqqqqqqqqqqqqq 02/19 23:01
推 nypgand1:請問"兩個in兩個out"是什麼意思阿? 可以舉一個轉過的圖嗎 02/19 23:43
推 KiroKu:我覺得沒差吧 a->B c->D路徑有重疊的話 代表其實 a->D c->B 02/19 23:48
推 cmuming:樓上如果發生"交叉"的話就不成立囉 02/20 23:05
→ sneak: 然後其他點和編如同原圖 https://daxiv.com 09/11 14:17