更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19619769

大意

一个餐厅在相继的 $N$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾（$i = 1, 2, \dots, N$）。餐厅可以购买新的餐巾，每块餐巾的费用为 $p$ 分；或者把旧餐巾送到快洗部，洗一块需 $m$ 天，其费用为 $f$ 分；或者送到慢洗部，洗一块需 $n$ 天（$n \gt m$），其费用为 $s$ 分（$s \lt f$）。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

思路

一道很好的费用流题目，我们做一下考虑。

最终，由于每天都需要 $r_i$ 块餐巾布，那么最终我们的最大流一定是 $\sum r_i$，但是由于题目中的条件导致我们一定能求出最大流为 $\sum r_i$，主要的问题是费用最小，考虑如何建模。

首先每天我们首先要要求在这天开始的时候，有 $r_i$ 块新餐巾，而经过使用，这些餐巾在这天结束的时候会变成脏餐巾，那么我们考虑拆点，将一天分为 $in$ 和 $out$，$in$ 表示每天开始的时候，$out$ 表示每天结束的时候。

首先，我们需要向 $i_{out}$ 注入脏餐巾，我们建立源点 $S$，用来产生脏餐巾，容量为 $r_i$，花费为 $0$，其次我们建立汇点 $T$ 用来接收干净的餐巾，那么由 $i_{in}$ 向 $T$ 连容量为 $r_i$ 花费为 $0$ 的边。这样一来，如果最大流跑不满，就说明不可行。

接下来考虑题目中的约束，为了使得每天的 $i_{out} \to T$ 的流量流满，其实就是满足题目中的每天买餐巾的需求，我们可以从源点 $S$ 向每个 $i_{in}$ 连容量为 $\infty$，花费为 $p$ 的边。

接下来是洗衣服的约束，我们只需要每天的 $i_{out} \to {(i + m)}_{in}$ 容量为 $\infty$，花费为 $f$ 的边，$i_{out} \to {(i + n)}_{in}$ 容量为 $\infty$，花费为 $s$ 的边。

这样一来，直接跑最小费用最大流即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 4005;
const int MAXM = 20005;
struct node{
    int u, v, nxt, c, w;
}e[MAXM * 2];

int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];

void init(){
    tot = 0;
    memset(h, -1, sizeof(h));
}

void add(int u, int v, int c, int w){
    e[tot] = {u, v, h[u], c, w};
    h[u] = tot ++;
    e[tot] = {v, u, h[v], 0, -w};
    h[v] = tot ++;
}

bool spfa(){
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    vis[S] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u];~i;i = e[i].nxt){
            int v = e[i].v;
            if(e[i].c > 0){
                if(d[v] > d[u] + e[i].w){
                    d[v] = d[u] + e[i].w;
                    pre[v] = i;
                    if(!vis[v]){
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    return (d[T] != 0x3f3f3f3f);
}

long long EK(){
    long long res = 0;
    while(spfa()){
        long long Min = 1e9;
        for(int i = T;i != S;i = e[pre[i]].u){
            Min = min(Min, (long long)e[pre[i]].c);
        }
        for(int i = T;i != S;i = e[pre[i]].u){
            e[pre[i]].c -= Min;
            e[pre[i] ^ 1].c += Min;
            res += e[pre[i]].w * Min;
        }
    }
    return res;
}

int N;
int a[MAXN];
int p, m, f, n, s;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("repair.in", "r", stdin);
//    freopen("repair.out", "w", stdout);
    cin >> N;
    init();
    for(int i = 1;i <= N;i ++){
    	cin >> a[i];
	}
	S = 0, T = 2 * N + 1;
	cin >> p >> m >> f >> n >> s;
	for(int i = 1;i <= N;i ++){
		add(S, i + N, a[i], 0);
		add(S, i, 1e9, p);
		add(i, T, a[i], 0);
		if(i + 1 <= N){
			add(i + N, (i + 1) + N, 1e9, 0);
		}
		if(i + m <= N){
			add(i + N, (i + m), 1e9, f);
		}
		if(i + n <= N){
			add(i + N, (i + n), 1e9, s);
		}
	}
	cout << EK() << endl;
    return 0;
}

将每天拆成两个点，i点用于接收干净餐巾，i'点用于接收脏餐巾，那么：

·从i向T连流量为Ri，费用为0的边，如果满流则表示当天的餐巾数量足够

·从S向i'连流量为Ri，费用为0的边，表示每天结束时接收到Ri块脏餐巾

·从S向i连流量为∞，费用为p的边，表示每天开始时购买餐巾

·从i'向i+m连流量为∞，费用为f的边，表示送快洗

·从i'向i+n连流量为∞，费用为s的边，表示送慢洗

·从i'向(i+1)'连流量为∞，费用为0的边，表示将脏餐巾留到下一天

之后求最小费用最大流即可