[理工] [Algo] 台大100-資工

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