[理工] 演算法幾題

作者: TEPLUN (mihanami)   2018-10-26 20:48:36
想請教大大們幾題演算法問題
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)嗎
作者: wilson50101 (我覺得我還不錯啊)   2018-10-26 21:17:00
95.2 max flow的量等價於min cut的量所以如果x 個mincut的邊每邊流量+y則mincut流量+xy所以maxflow也+xy再加上原來的f就是答案了
作者: TEPLUN (mihanami)   2018-10-26 21:48:00
所以那個arc是指單方向邊的意思嗎 瞭解了謝謝
作者: FRAXIS (喔喔)   2018-10-30 10:47:00
第二題 你要找一下關於有流量上下限的 network flow 解法

Links booklink

Contact Us: admin [ a t ] ucptt.com