AC. 梦想

frank_c1

[BZOJ 2424] 订货

发布于2016年03月19日 | 暂无评论 | 422阅读 | 费用流

题目描述

某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为S。

输入格式

第1行:n, m, S (0<=n<=50, 0<=m<=10, 0<=S<=10000)

第2行:U1 , U2 , ... , Ui , ... , Un (0<=Ui<=10000)

第3行:d1 , d2 , ..., di , ... , dn (0<=di<=100)

输出格式

只有1行,一个整数,代表最低成本。

题目解析

又是一发餐巾计划问题。

分析一下题目条件,建模如下:

1.按月数建点,设第i月为X_i

2.建源stsX_i连容量为无穷大,费用为d_i的边,表示该月订单。

3.X_it连容量为U_i,费用为0的边,表示当月的需求量。

4.X_iX_{i+1}连容量为S,费用为m的边,表示第i月贮存下来的产品。

跑最小费用最大流即可。感觉这种类餐巾计划问题形式还是蛮统一的。