BZOJ 2424: [HAOI2010] 订货

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


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

题意:市场在第 i 个月对某产品的需求量为\(U_i\),在第 i 月订货单价为\(d_i\),上个月未销完的单位产品要付存贮费用 m,问如何安排这 n 个月订购计划,使成本最低。每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为 S。


也就只能会做这种费用流了...

约定

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

抽象每个月为点 1-n 建模如下

for i=1~n (S,i,inf,d[i]) 第 i 个月购买费用

for i=1~n (i,T,u[i],0); 每个月必须出售 u[i]

for i=1~n-1 (i,i+1,s,m) 存贮费用

 


一个非常弱的准退役OIER