BZOJ 2424: [HAOI2010] 订货


题目链接: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) 存贮费用

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2424: [HAOI2010] 订货


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,