题解 【P1251 餐巾计划问题】

非常神奇的一个trick。

开始看错题想成了NOI2008的那道志愿者招募，结果写出来过不了样例（（（

这题每天其实分为两个动作，花掉干净的餐巾和洗不干净的餐巾。

所以拆成两个点，一个是这一天用餐巾的时候（简称消耗点），一个是洗净不干净的餐巾的时候（简称洗净点）。

从源点向第 $i$ 天的消耗点连边，容量为 $r_i$，费用自然是 $0$。同理，从这一天的洗净点向汇点连边，容量费用同上。

再从原点向第 $i$ 天开始点连一条容量为 INF，费用为 $p$ 的边，代表买新的餐巾。

从第 $i$ 天的洗净点向第 $i+1$ 天的洗净点连边，流量为 INF，费用为 $0$，表示这一天不干净的餐巾可以堆到明天。

从第 $i$ 天的洗净点向第 $i+m$ 天的消耗点连边，流量为 INF，费用为 $f$，表示第 $i$ 天送到快洗部，第 $i+m$ 天洗好了可以直接用。

从第 $i$ 天的洗净点向第 $i+n$ 天的消耗点连边，流量为 INF，费用为 $s$，表示第 $i$ 天送到慢洗部，第 $i+n$ 天洗好了可以直接用。

跑个费用流就行了。

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, cap, cost;
} e[200005];
int head[50005], cur[50005], dis[50005], s, t, tot = 1, N;
bool mark[50005], vis[50005];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap, const int cost) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}

bool SPFA() {
	memcpy(cur, head, sizeof cur);
	memset(mark, 0, sizeof mark);
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s] = 0;
	Q.push(s);
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int i(head[u]); i; i = e[i].nxt) {
			int v(e[i].to);
			if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] <= INF;
}

int dfs(const int u, const int flow) {
	if (u == t) return flow;
	vis[u] = true;
	int used(0), tmp(0);
	for (int i(cur[u]); i; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dis[u] + e[i].cost == dis[e[i].to] && !vis[e[i].to]) {
			tmp = dfs(e[i].to, min(flow - used, e[i].cap));
			e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
			if (used == flow) return used;
		}
	}
	if (!used) dis[u] = 0;
	return used;
}

int Dinic() {
	int Maxflow(0), Mincost(0), flow(0);
	while (SPFA()) Maxflow += (flow = dfs(s, INF)), Mincost += flow * dis[t];
	return Mincost;
}

signed main() {
	int p, m, f, n, s;
	scanf("%lld", &N);
	s = 0, t = 2 * N + 1;
	for (int i(1); i <= N; ++ i) {
		int x;
		scanf("%lld", &x);
		AddEdge(0, i + N, x, 0);
		AddEdge(i, t, x, 0);
	}
	scanf("%lld%lld%lld%lld%lld", &p, &m, &f, &n, &s);
	for (int i(1); i <= N; ++ i) {
		AddEdge(0, i, INF, p);
		if (i < N) AddEdge(i + N, i + N + 1, INF, 0);
		if (i + m <= N) AddEdge(i + N, i + m, INF, f);
		if (i + n <= N) AddEdge(i + N, i + n, INF, s);
	}
	printf("%lld", Dinic());
	return 0;
}