首页 > 代码库 > [bzoj2245][SDOI2011]工作安排(费用流)

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

题目: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]工作安排(费用流)