线性规划与网络流24式 第10式 餐厅计划问题

@vrqq  December 29, 2017
https://www.oj.swust.edu.cn/problem/show/1745

一个简单的费用流,很久很久以前在vijos上做过类似的,有些启发,简单写写。
刚开始想远了,先想了上下界费用流,然后看转化成最大流能不能符合题目。一琢磨应该很容易,仔细想了想,可拆点,拆完点做不成网络流,兴许还能做dp不是。

题目变量定义

R[i] 每天需要的napkin数量
buyPrice 买新的价格。
fastDay 走快洗需要几天(例子1天),fastPrice 快洗价钱。
slowDay 走慢洗几天(例子2天),slowPrice 慢洗多少钱。

一个错误的例子

先想到了按每天拆点,把每天拆成开始和结束,有了这个图:
error1-1.png error1-1.xml
(来自http://draw.io) (p.s. Mac用户推荐brew graphviz)
问题在于,想得美啊,如果求了最大流,那个fastClean和slowClean根本就不能走!因为首先要满足最大流,于是我们可以这样改一下。

再加一层,做一个受控电流源(CCCS)出来

比如第一天可以给第2、第3天供货,那么加边S->provider1->day2BeginS->provider2->day3Begin,见下图。
correct.pngcorrect.xml
然后删掉多余边,终了。

另外一个测时间小技巧,极为好用!

g++ prog.cpp -o prog
time ./prog < testData.in

添加新评论