[理工] 算法几题

楼主: 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