[理工] 演算法幾題

看板Grad-ProbAsk作者 (mihanami)時間7年前 (2018/10/26 20:48), 編輯推噓2(2推 0噓 3→)
留言5則, 3人參與, 7年前最新討論串1/1
想請教大大們幾題演算法問題 1. https://i.imgur.com/bCzgdf3.jpg
95.2不懂這式子怎麼來的... 2. https://i.imgur.com/WiiXGrN.jpg
題目說每個paper「至少」要分給兩個志願者 但照這張圖s~Pi容量皆設為2，應該代表「至多」分配給兩位志願者吧？ 再者，題目定義每個paper都要分配給至少兩個不同的志願者 那代表6種paper至少會發出12張吧？這樣第二題答案也不合理 不知道我是不是哪邊搞錯了@@ 3. https://i.imgur.com/kEKl0gg.jpg
https://i.imgur.com/L27xHvG.jpg
看了一下第二題還是不懂他在問什麼...有請神人解答 4. https://i.imgur.com/YUwpLsD.jpg
請問第二題c的敘述該如何改才對？是O(E)嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.137.199 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1540558118.A.5D6.html
推
10/26 21:17, 7年前 , 1F
95.2 max flow的量等價於min cut的量
10/26 21:17, 1F
→
10/26 21:17, 7年前 , 2F
所以如果x 個mincut的邊每邊流量+y則mincut流量+xy
10/26 21:17, 2F
→
10/26 21:17, 7年前 , 3F
所以maxflow也+xy再加上原來的f就是答案了
10/26 21:17, 3F
→
10/26 21:48, 7年前 , 4F
所以那個arc是指單方向邊的意思嗎 瞭解了謝謝
10/26 21:48, 4F
推
10/30 10:47, 7年前 , 5F
第二題 你要找一下關於有流量上下限的 network flow 解法
10/30 10:47, 5F
‣ 更多 TEPLUN 的文章
文章代碼(AID): #1RqmqcNM (Grad-ProbAsk)