OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2001】软件开发

【题目描述】

某软件公司正在规划一项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.

【输出】

最少费用.

【输入样例】

4 1 2 3 2 1

8 2 1 6

【输出样例】

38

【数据范围】

1≤f,fA,fB≤60,1≤n≤1000

【题解】

感觉自己不太会做的样子o(╯□╰)o

第i天会使用ni条毛巾,会留下ni条需要处理的毛巾,因此我们把每一天拆成两个点,其中x[i]表示第i天使用的毛巾,y[i]表示第i天留下的毛巾,然后按照如下方式建边来达到限制并求出最小费用:

①x[i]向汇点T建边,容量为ni,费用为0,表示第i天需要使用ni条毛巾;

②源点S向y[i]建边,容量为ni,费用为0,表示第i天多出ni条毛巾待处理;

③源点S向x[i]建边,容量为INF,费用为f,表示直接购买新毛巾以供使用;

④y[i]向y[i+1]建边,容量为INF,费用为0,表示把第i天待处理的毛巾留到第i+1天处理;

⑤y[i]向x[i+a+1]建边,容量为INF,费用为fA,表示第i天的毛巾进行A种消毒;

⑥y[i]向x[i+b+1]建边,容量为INF,费用为fB,表示第i天的毛巾进行B种消毒。

容易发现最后①②连出的边会成为割边,因此所有限制被满足。而剩下的连边方式描述了所有情况,故做一次费用流即能得到最优解,这也是整道题的精华所在:割边表示限制,描述所有情况后利用网络流出解。

【代码】

感觉是网络流24题里的原题啊?总之1A了~

http://paste.ubuntu.com/11721137/

评论

© OI技术宅 | Powered by LOFTER