能不能说下思路……你这样的话~~我这种阅读能力0的菜鸡~~可能很难看懂
by Refun @ 2018-05-03 16:27:34
突然发现今天还没有%过@[Refun](/space/show?uid=41890) orz [Refun](/space/show?uid=41890)
by λᴉʍ @ 2018-05-03 16:30:46
@[Refun](/space/show?uid=41890)
1.从原点向每一天晚上连一条流量为当天所用餐巾x,费用为0的边,表示每天晚上从起点获得x条脏餐巾。
2.从每一天早上向汇点连一条流量为当天所用餐巾x,费用为0的边,每天白天,表示向汇点提供x条干净的餐巾,流满时表示第i天的餐巾够用 。 3.从每一天晚上向第二天晚上连一条流量为INF,费用为0的边,表示每天晚上可以将脏餐巾留到第二天晚上(注意不是早上,因为脏餐巾在早上不可以使用)。
4.从每一天晚上向这一天+快洗所用天数t1的那一天早上连一条流量为INF,费用为快洗所用钱数的边,表示每天晚上可以送去快洗部,在地i+t1天早上收到餐巾 。
5.同理,从每一天晚上向这一天+慢洗所用天数t2的那一天早上连一条流量为INF,费用为慢洗所用钱数的边,表示每天晚上可以送去慢洗部,在地i+t2天早上收到餐巾 。
6.从起点向每一天早上连一条流量为INF,费用为购买餐巾所用钱数的边,表示每天早上可以购买餐巾 。 注意,以上6点需要建反向边!3~6点需要做判断(即连向的边必须<=n)
然后ZKW
by 爱喝敌敌畏 @ 2018-05-03 16:31:11
@[敌敌畏](/space/show?uid=65602) 做的挺久了细节我也忘了~~懒得看了~~……给你贴一下我当时做的时候写的题解吧QAQ
```cpp
//具体做法:
//拆点,将i点拆为xi和yi
//xi用来处理脏餐巾
//yi用来提供当天需要的餐巾
//很容易得出一部分连边:
//S--yi--T,第一条容量为INF,费用为New。意为可以无限购买
// 第二条容量为第i天需要的数量,费用为0。其实就是用来限制一下当天的流量
//S--xi 容量为第i天需要的数量,费用为0,意为当天可以多?块脏餐巾
//
//接下来就是我之前写法里没有的地方了
//xi--x(i+1),容量INF,费用0,意为把上一天的脏餐巾继承下来
//然后就是xi和快/慢洗天数后的yi连边,意为第j天可以用第i天的脏餐巾,容量INF,费用如题
//再跑裸的最小费用最大流即可。
```
by Refun @ 2018-05-03 16:35:44
@[Refun](/space/show?uid=41890) 谢谢
by 爱喝敌敌畏 @ 2018-05-03 16:38:31
@[敌敌畏](/space/show?uid=65602) ~~QAQ还是我太菜了~~
by Refun @ 2018-05-03 16:39:23
@[Refun](/space/show?uid=41890) Orz [Refun](/space/show?uid=41890) 进队了说自己菜!
by λᴉʍ @ 2018-05-03 16:39:57
@[Refun](/space/show?uid=41890) 可是是超时,检查了多处也并没有错
by 爱喝敌敌畏 @ 2018-05-03 16:50:40
不能用ZKW!
要用连续SPFA呀!
by 爱喝敌敌畏 @ 2018-05-04 10:14:29