作者TEPLUN (mihanami)
看板Grad-ProbAsk
标题[理工] 演算法几题
时间Fri Oct 26 20:48:36 2018
想请教大大们几题演算法问题
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1540558118.A.5D6.html
1F：推 wilson50101: 95.2 max flow的量等价於min cut的量 10/26 21:17
2F：→ wilson50101: 所以如果x 个mincut的边每边流量+y则mincut流量+xy 10/26 21:17
3F：→ wilson50101: 所以maxflow也+xy再加上原来的f就是答案了 10/26 21:17
4F：→ TEPLUN: 所以那个arc是指单方向边的意思吗 了解了谢谢 10/26 21:48
5F：推 FRAXIS: 第二题 你要找一下关於有流量上下限的 network flow 解法 10/30 10:47