Olympiad in Informatics Beginners' Home » 提高-讨论区 » 最小费用最大流用最小费用路增广算法，每一次增广的价值和是不升的吗？

antoniowyn 发表于 2008-11-20 10:10 PM

最小费用最大流用最小费用路增广算法，每一次增广的价值和是不升的吗？

最小费用最大流用最小费用路增广算法，每一次增广的价值和是不升的吗？
比方说，第一次增广时单位流量总费用增加了k，第二次增广是单位流量总费用增加了k'，总有k'<=k，对吗？ （注意：费用增加指的是单位流量）

fjxmlhx 发表于 2008-11-20 10:15 PM

应该是吧，若存在k'<k那么第一次求出来的一定不是K

cai0715 发表于 2008-11-20 10:42 PM

不懂。。。

風若吹 发表于 2008-11-21 11:37 PM

嗯，是对的

liucong 发表于 2008-11-22 01:12 AM

k<=k'

jason911 发表于 2008-11-22 07:40 AM

[quote]k
[size=2][color=#999999]liucong 发表于 2008-11-22 01:12[/color] [url=http://www.oibh.org/bbs/redirect.php?goto=findpost&pid=321901&ptid=27242][img]http://www.oibh.org/bbs/images/common/back.gif[/img][/url][/size][/quote]
聪傻子你打反了

查看完整版本: 最小费用最大流用最小费用路增广算法，每一次增广的价值和是不升的吗？