BZOJ 1221 [HNOI2001] 软件开发

发布于 2017-06-23  166 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1221

题意:n 天,每天需要\(n_i\) 个毛巾,毛巾用了会脏,有 a,b 两种洗毛巾方式,用时和价格不同,还可以买新毛巾,求最小费用...


真的是... 差一点就建出来图了... 想到拆点,“洗毛巾”这个操作也抽象出来了,就是出入点之间连一连,但是不知道怎么处理流量,想到最大流应该是\(\sum_{i=1}^{n}n_i \),然而不会做了...

约定

在本题解中,形如 (a,b,i,j) 的四元组意为从 a 连向 b 一条流量为 i,费用为 j 的边

说一下题解建模吧:

点 0 为 S 点,点 1-n 为拆点后入点,点 n+1-2*n 为拆点后出点,点 2*n+1 为 T 点

for i=1~n (S,i,\(n_i\),0) 为每天分配一条“脏的”毛巾

for i=1~n (S,i+n,inf,f) 每天可以直接购买一条"干净的"毛巾

for i=1~n (i+n,T,p[i],0) 每天必须有\(n_i\) 条干净的毛巾被"使用",我们以流进汇点抽象这个过程

for i=1~n-1 (i,i+1,inf,0) 每天的"脏"毛巾可以不洗,则累计进下一天

for i=1~n-a-1 (i,i+a+1+n,inf,fa) 每天的脏毛巾可以用 a 方式洗 a+1 天后可以使用

for i=1~n-b-1 (i,i+b+1+n,inf,fb) 每天的脏毛巾可以用 b 方式洗 b+1 天后可以使用

over

 


一个非常弱的准退役OIER