AC. 梦想

frank_c1

[BZOJ 1221] 软件开发

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

题目描述

某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB,而买一块新毛巾的费用为f(新毛巾是已消毒的,当天可以使用);而且f>fA>fB。公司经理正在规划在这n天中,每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然,公司经理希望费用最低。你的任务就是:为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒,使公司在这项n天的软件开发中,提供毛巾服务的总费用最低。

输入格式

第1行为n,a,b,f,fA,fB. 第2行为n1,n2,……,nn. (注:1≤f,fA,fB≤60,1≤n≤1000)

输出格式

最小费用。

题目解析

和网络流24题中“餐巾计划问题”相似。

题目的限制条件有点多,我们来逐条分析建模:

1.每天用完的毛巾和供应的毛巾的量应该是相同的,第i天为n_i。基于这个思想,建源st,把天数分为X,Y两部,X_i代表第i天用完的,Y_i代表第i天供应的。sX_i连容量为n_i,费用为0的边,Y_it连容量为n_i,费用为0的边。

2.sY_i连容量为无穷大,费用为f的边,表示买入的毛巾。

3.X_iY_{i+a+1}连容量为无穷大,费用为fA的边,表示A种消毒方式。

4.X_iY_{i+b+1}连容量为无穷大,费用为fB的边,表示B种消毒方式。

5.X_iX_{i+1}连容量为无穷大,费用为0的边,今天洗不完的毛巾明天洗。

跑最小费用最大流即可。看起来还是很显然的吧。