https://www.oj.swust.edu.cn/problem/show/1745
一个简单的费用流,很久很久以前在vijos上做过类似的,有些启发,简单写写。
刚开始想远了,先想了上下界费用流,然后看转化成最大流能不能符合题目。一琢磨应该很容易,仔细想了想,可拆点,拆完点做不成网络流,兴许还能做dp不是。
题目变量定义
R[i] 每天需要的napkin数量
buyPrice 买新的价格。
fastDay 走快洗需要几天(例子1天),fastPrice 快洗价钱。
slowDay 走慢洗几天(例子2天),slowPrice 慢洗多少钱。
一个错误的例子
先想到了按每天拆点,把每天拆成开始和结束,有了这个图:
error1-1.xml
(来自http://draw.io) (p.s. Mac用户推荐brew graphviz)
问题在于,想得美啊,如果求了最大流,那个fastClean和slowClean
根本就不能走!因为首先要满足最大流,于是我们可以这样改一下。
再加一层,做一个受控电流源(CCCS)出来
比如第一天可以给第2、第3天供货,那么加边S->provider1->day2Begin
和S->provider2->day3Begin
,见下图。
correct.xml
然后删掉多余边,终了。
另外一个测时间小技巧,极为好用!
g++ prog.cpp -o prog
time ./prog < testData.in