图论 3

矩阵树定理

无

见专题部分

Codeforces Round #658 (Div. 2) pro:4/5/6 rk:1181/14672

cf658 div2

构造

给定一个01序列，可以翻转前k位，并将0换成1，1换成0，输出一种可行的方案，得到目标串。

由于翻转前面的数位不影响后面的数字，所以从后向前枚举每一位，找到能得到与目标串第I位相同的一种翻转方案。

洛谷p1251

网络流

一个餐厅第 $i$ 天需要 $r_i$ 条新餐巾，每条新餐巾用完后得到旧餐巾，一开始餐厅没有餐巾。

买一条新餐巾费用为 $p$；快洗一条旧餐巾时间为 $m$ 天，费用为 $f$；慢洗一条旧餐巾时间为 $n$ 天，费用为 $s$。

数据保证 $f\gt s,m\lt n$，问餐厅营业 $N$ 天的最小花费。

把一天分成一天的开始和一天的结束，一天的开始需要提供 $r_i$ 条新餐巾，于是连一条容量为 $r_i$ 费用为 $0$ 的边到汇点。

接下来考虑三种获取新餐巾的操作。首先可以买新餐巾，对应源点连一条容量为 $\inf$ 费用为 $p$ 的边到当天的开始。

另外也可以通过清洗之前的旧餐巾获得。不妨假设如果旧餐巾洗完就会被立即使用，不然可以留到以后再洗。这样假设的目的是减少连边数量。

于是第 $i$ 天的结束向第 $i+m$ 天的开始连一条容量为 $\inf$ 费用为 $f$ 的边，向第 $i+n$ 天的开始连一条容量为 $\inf$ 费用为 $s$ 的边。

再考虑维护旧餐巾，旧餐巾可以通过两种方式获取。

首先一天的结束将有 $r_i$ 条新餐巾变成旧餐巾，于是从源点连一条容量为 $r_i$ 费用为 $0$ 的边到一天的结束。

另外旧餐巾也可以继承前一天剩下的未被清洗的旧餐巾，对应每天结束向第二天结束连一条容量为 $\inf$ 费用为 $0$ 的边。

最后跑最小费用最大流即可。

一道比较考察建模能力的网络流题。