[理工] 演算法幾題

[TEPLUN (mihanami)]

想請教大大們幾題演算法問題
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
推 wilson50101: 95.2 max flow的量等價於min cut的量
→ wilson50101: 所以如果x 個mincut的邊每邊流量+y則mincut流量+xy
→ wilson50101: 所以maxflow也+xy再加上原來的f就是答案了
→ TEPLUN: 所以那個arc是指單方向邊的意思嗎 瞭解了謝謝
推 FRAXIS: 第二題 你要找一下關於有流量上下限的 network flow 解法