餐巾
餐巾计划问题
餐巾计划问题 先拆点，将每天拆成两个点，一个表示用完的旧餐巾①，一个表示需要的新餐巾②。 考虑几种边： 购买边，从起点往②点连 \(\inf,p\)。 快洗边，从前 \(m\) 天往②点连 \(\inf,p\)。 慢洗边，从前 \(n\) 天往②点连 \(\inf,f\)。 容量限制边 从②点往终点 ......
P1251 餐巾计划问题（拆点）
最小总花费，因为$ria_{i+m}$费用为$f$，流量为$\inf$的边 $3$、考虑将肮脏的餐巾送到慢洗部，连一天$a_{i+N}->a_{i+n}$费用为$s$，流量为$\inf$的边 $4$、因为我们若将肮脏的餐巾送到慢洗部和快洗部，根据网络流本质上是贪心算法，所以我们要按照他的性质来进行下 ......
P1251 餐巾计划问题
一个餐厅在相继的 N 天里,每天需用餐巾。假设第 i天需要 A[i]块餐巾( i=1,2,...,N)。 餐厅可以购买新的餐巾,每块餐巾的费用为 p 分; 或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分; 或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs< ......