GG热腾腾的电面

dydcfg 发表于 2016-9-9 09:33
假设源点是s,然后每个人的点是p1,p2...pn.
建图的时候capacity=1,这样确保每个人最多只有1的流量汇入 ...

我有点忘记了。。那中间那些流你不是记录费用吗？那如果人node流入只有1，那流出的费用不是只限定成1吗？

xihaokai1 发表于 2016-9-9 09:36
我有点忘记了。。那中间那些流你不是记录费用吗？那如果人node流入只有1，那流出的费用不是只限定成1吗？

唔,你的link应该是给的最大流.最小费用最大流比最大流多了一个费用属性,每条边除了容量属性外,还多了一个费用的属性.
解法画了个图

dydcfg 发表于 2016-9-9 09:53
唔,你的link应该是给的最大流.最小费用最大流比最大流多了一个费用属性,每条边除了容量属性外,还多了一个 ...

好的，我研究一下，十分感谢

xihaokai1 发表于 2016-9-9 09:54
好的，我研究一下，十分感谢

客气啦～

有必要这么难么...

ofdk88 发表于 2016-9-10 15:59
想问楼主后来有回应吗？

哦哦， 忘了说，第二天拿到onsite 了