网络流练习笔记
无
一些常用的套路：
- 必须完成的一些目标，可以考虑搞进流量中，因为跑最大流的话肯定会流满，也就相当于强制地完成了那些目标。
- 拆点。然后可以通过两点之间连某个容量的边来限制该点取到的次数。
- 建立超级源点、汇点。几乎在每道题中都会用到，不光方便计算，还可以通过连边的方式对某些状态进行操作。
P1251 餐巾计划问题
发现每天开始和结束时的状态是不一样的，考虑拆点。
接着怎么办？模拟餐巾的路线吗？
假如从白天向晚上连一条边表示餐巾由干净变为脏的话，会发现根本无法处理每天的需求量。
那反正只要是干净的就行了，咋来的咱不管，那就直接从超级源点流过来嘛。然后就可以让餐巾流到超级汇点来完成需求啦！
具体分以下几种：
- 由超级源点向每天晚上连一条容量为当日需求，费用为 \(0\) 的边。表示晚上获得脏餐巾。
- 由每天早上向超级汇点连一条容量为当日需求，费用为 \(0\) 的边。表示白天需要新餐巾。
- 由每天晚上向次日晚上连一条容量为 \(\infty\)，费用为 \(0\) 的边。表示餐巾不洗留到下一天。
- 由每天晚上向现在送去快洗能洗好的那天早上连一条容量为 \(\infty\)，费用为快洗费用的边。表示送去快洗。
- 由每天晚上向现在送去慢洗能洗好的那天早上连一条容量为 \(\infty\)，费用为慢洗费用的边。表示送去慢洗。
- 由超级源点向每天早上连一条容量为 \(\infty\)，费用为购买新餐巾费用的边。表示购买新餐巾。
值得注意的是，第三点处于贪心的考虑，肯定会直接洗掉。但我们发现设计的方案中并没有设置这样一个库存餐巾，所以就得通过这一步来使得餐巾能够在必须洗的那天晚上刚好洗掉，从而达到和提前洗完一样的效果。所以如果某天晚上就算送去快洗也洗不完了，前一天晚上的这条边可以不连。
版权声明：本文为May-2nd原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。