首页 > 其他 > 详细

[bzoj2245][SDOI2011]工作安排(费用流)

时间:2014-12-02 23:55:04      阅读:885      评论:0      收藏:0      [点我收藏+]

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2245

分析:

要注意到题目下面说的w是单增的

明显的费用流:

弄个源点S,汇点T

S连向每种产品,流量是这种产品所需个数,费用是0

每种产品连向能制作它的人,流量为inf,费用是0

每个人向T连Si+1条边,流量t[i][j]-t[i][j-1],费用w[i][j]

(因为w是单增的,所以就保证了每个人连向T的Si+1条边肯定是上面的边填满之后再填下面的边,保证了符合题意,如果没有这个w单增的条件,则不行,因为如果右面某个w比前面的w小,则会直接填后面,而前面则不会填,这样不符合题意。)

最后跑个最小费用最大流就可以了

[bzoj2245][SDOI2011]工作安排(费用流)

原文:http://www.cnblogs.com/wmrv587/p/4138833.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!