题面

餐巾计划问题

题解

隐式图问题。
我们考虑建立分层图，那么每层的状态即为时间，将每天拆成两个点，分别表示早上和晚上。

1. 从源点向表示晚上的点连流量为当天所用餐巾数 \(r_i\)，费用为 \(0\) 的边，表示每天晚上得到 \(r_i\) 条脏餐巾。
2. 从表示早上的点向汇点连流量为当天所用餐巾数 \(r_i\)，费用为 \(0\) 的边，表示每天早上用了 \(r_i\) 条餐巾，流满证明够用。
3. 从每一天晚上向第二天晚上练流量为 \(inf\), 费用为 \(0\) 的边，表示把脏餐巾留到下一天晚上，因为不能留给下一天早上，所以不能向下一天早上连。
4. 从每一天晚上向快洗时间之后的早上连流量为 \(inf\), 费用为快洗费用的边，表示把脏餐巾送去快洗，洗完之后的那天早上就能用了。
5. 慢洗同理。
6. 从源点向每天早上连流量为 \(inf\), 费用为购买餐巾费用的边，表示早上购买新餐巾。
   然后跑最小费用最大流就好了，最大流保证了餐巾够用，最小费用保证了花费最少。

代码

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 4e3 + 5, M = 1e5 + 5;
const LL inf = 1e17;

int head[N], nex[M], to[M], c[M], n, tot = 1;
int S, T, t1, t2, w1, w2, p; LL maxflow = 0, ans = 0, w[M];

inline void add(int u, int v, int k, LL f) {
	nex[++tot] = head[u]; to[tot] = v; w[tot] = f; c[tot] = k; head[u] = tot;
	nex[++tot] = head[v]; to[tot] = u; w[tot] = 0; c[tot] = -k; head[v] = tot;
}

namespace Edmonds_Karp {
	int pre[N]; LL dis[N], incf[N]; bool inq[N];
	queue < int > q;
	inline bool SPFA() {
		for(int i = 0; i < N; i++) dis[i] = inf;
		memset(inq, false, sizeof inq);
		dis[S] = 0; q.push(S); inq[S] = true; incf[S] = inf;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			inq[x] = false;
			for(int i = head[x]; i; i = nex[i]) {
				if(!w[i]) continue;
				if(dis[to[i]] > dis[x] + c[i]) {
					dis[to[i]] = dis[x] + c[i];
					incf[to[i]] = min(incf[x], w[i]);
					pre[to[i]] = i;
					if(!inq[to[i]]) q.push(to[i]), inq[to[i]] = true;
				}
			}
		}
		return dis[T] < inf;
	}
	inline void update() {
		int x = T;
		while(x != S) {
			int i = pre[x];
			w[i] -= incf[T], w[i ^ 1] += incf[T];
			x = to[i ^ 1];
		}
		maxflow += incf[T];
		ans += dis[T] * incf[T];
	}
}

using namespace Edmonds_Karp;

int main() {
	scanf("%d", &n);
	S = 0; T = 2 * n + 1;
	for(int i = 1, x; i <= n; i++) scanf("%d", &x), add(S, i + n, 0, x), add(i, T, 0, x);
	scanf("%d%d%d%d%d", &p, &t1, &w1, &t2, &w2);
	for(int i = 1; i <= n; i++) {
		add(S, i, p, inf);
		if(i + t1 <= n) add(i + n, i + t1, w1, inf);
		if(i + t2 <= n) add(i + n, i + t2, w2, inf);
		if(i < n) add(i + n, i + 1 + n, 0, inf);
	}
	while(SPFA()) update();
	printf("%lld\n", ans);
	return 0;
}