P1251 餐巾计划问题
大意
一个餐厅在相继的 \(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;
}