[理工] 演算法 圖論

看板Grad-ProbAsk作者 (Mistel)時間6年前 (2019/09/23 00:52), 6年前編輯推噓6(6推 0噓 5→)
留言11則, 4人參與, 6年前最新討論串2/3 (看更多)
https://i.imgur.com/86wzad1.jpg
請問第三小題的敘述一定成立嗎？ 立宇老師上課是說maximal flow problem拿來解決所有有理數，那maximal flow不是應該有 可能有分數嗎？ 第47題 https://i.imgur.com/WveKymu.jpg
請問這題的是要做什麼？看不懂題意 第43題第2小題的(c)選項 https://i.imgur.com/ePS3fSn.jpg
https://i.imgur.com/uYcTt3e.jpg
雖然我直覺選下去了但我看不懂@@ 請問w(ai)<=w(ei)是什麼意思？ 為什麼G中的任意點ai也會有權重？ 我看題目並沒有更新過G中各點的權重，回去翻kruskal's也沒有調整過點的權重啊@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.50.75 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1569171135.A.395.html
推
09/23 10:31, 6年前 , 1F
一般都只討論整數的情況 因為分數你只要全部乘以最小公倍
09/23 10:31, 1F
→
09/23 10:31, 6年前 , 2F
數就變成整數了
09/23 10:31, 2F
推
09/23 10:33, 6年前 , 3F
47 題就只是問當 edge weight 有上限時 如何實作
09/23 10:33, 3F
→
09/23 10:33, 6年前 , 4F
priority queue 來加速
09/23 10:33, 4F
感謝F大！ 另外再請教一下為什麼第二小題在這種情況下會用到雙向鏈結呢？看不懂解答的建法為什麼 是這樣子 補充另一半的解答 https://i.imgur.com/vhSMZrS.jpg
推
09/23 11:14, 6年前 , 5F
09/23 11:14, 5F
剛剛有翻到原文書的intergrality theorem這邊 https://i.imgur.com/VS6gxpW.jpg
所以我可以理解為 若圖上所有邊的capacity為整數，則使用ford fulkerson會得到最大流量f為整數，且對於 所有在圖上的點u,v，u到v的流量為整數 但其實流量f的解並不一定必需是整數，只是用ford-fulkerson跑出來會是，這樣對嗎？
推
09/23 11:27, 6年前 , 6F
09/23 11:27, 6F
哦哦哦，犯蠢了，感謝mi大 ※ 編輯: mistel (223.137.50.75 臺灣), 09/23/2019 13:04:29 ※ 編輯: mistel (223.137.50.75 臺灣), 09/23/2019 13:14:59
推
09/23 16:07, 6年前 , 7F
嗯嗯對的（話說原來書上有這個定理@@該添購了）
09/23 16:07, 7F
→
09/23 17:53, 6年前 , 8F
課本上通常一個算法大概Lenma加上定理應該有十多個XD，mi
09/23 17:53, 8F
→
09/23 17:53, 6年前 , 9F
大可以去compbook徵，蠻好徵的~
09/23 17:53, 9F
→
09/23 20:19, 6年前 , 10F
(1)對 maximum flow和是不是分數沒關
09/23 20:19, 10F
推
09/23 21:51, 6年前 , 11F
雙向鏈結只是拿來存同 priority 的 nodes
09/23 21:51, 11F
‣ 更多 mistel 的文章
文章代碼(AID): #1TXwQ_EL (Grad-ProbAsk)
‣ 更多 mistel 的文章
文章代碼(AID): #1TXwQ_EL (Grad-ProbAsk)