作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 演算法 圖論
時間Mon Sep 23 00:52:13 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1569171135.A.395.html
1F：推 FRAXIS: 一般都只討論整數的情況 因為分數你只要全部乘以最小公倍09/23 10:31
2F：→ FRAXIS: 數就變成整數了09/23 10:31
3F：推 FRAXIS: 47 題就只是問當 edge weight 有上限時 如何實作09/23 10:33
4F：→ FRAXIS: priority queue 來加速09/23 10:33
感謝F大！
另外再請教一下為什麼第二小題在這種情況下會用到雙向鏈結呢？看不懂解答的建法為什麼
是這樣子
補充另一半的解答
https://i.imgur.com/vhSMZrS.jpg
剛剛有翻到原文書的intergrality theorem這邊
https://i.imgur.com/VS6gxpW.jpg
所以我可以理解為
若圖上所有邊的capacity為整數，則使用ford fulkerson會得到最大流量f為整數，且對於
所有在圖上的點u,v，u到v的流量為整數
但其實流量f的解並不一定必需是整數，只是用ford-fulkerson跑出來會是，這樣對嗎？
哦哦哦，犯蠢了，感謝mi大
※ 編輯: mistel (223.137.50.75 臺灣), 09/23/2019 13:04:29
※ 編輯: mistel (223.137.50.75 臺灣), 09/23/2019 13:14:59
7F：推 mi981027: 嗯嗯對的（話說原來書上有這個定理@@該添購了） 09/23 16:07
8F：→ mistel: 課本上通常一個算法大概Lenma加上定理應該有十多個XD，mi 09/23 17:53
9F：→ mistel: 大可以去compbook徵，蠻好徵的~ 09/23 17:53
10F：→ mathtsai: (1)對 maximum flow和是不是分數沒關 09/23 20:19
11F：推 FRAXIS: 雙向鏈結只是拿來存同 priority 的 nodes 09/23 21:51