luogu P1251 餐巾计划问题（网络流24题 费用流 + 拆点建图）
题目描述
一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入格式
由标准输入提供输入数据。文件第 1 行有 1 个正整数 NN，代表要安排餐巾使用计划的天数。
接下来的一行是餐厅在相继的 NN 天里,每天需用的餐巾数。
最后一行包含5个正整数p,m,f,n,sp,m,f,n,s。pp 是每块新餐巾的费用; mm 是快洗部洗一块餐巾需用天数; ff 是快洗部洗一块餐巾需要的费用; nn 是慢洗部洗一块餐巾需用天数; ss 是慢洗部洗一块餐巾需要的费用。
输出格式
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
输入输出样例
3 1 7 5 11 2 2 3 1
输出
134
说明/提示
N<=2000
ri<=10000000
p,f,s<=10000
时限4s
思路：
设每天需要ned[i]个餐巾。把每一天拆成早晨和晚上，s = 0为超级源点，t = 2 * n + 1为超级汇点。如下建图：
（1）s向每天晚上连边，每天晚上都会有当天剩下的脏餐巾，流量为ned[i]，费用为0
（2）每天早晨向t连边，每天早晨需要ned[i]个干净的餐巾，流量为ned[i]，费用为0
（3）每天晚上都可以把脏餐巾留到以后再洗，前一天晚上向第二天晚上连边，流量为inf，费用为0
（4）每天晚上可以把脏餐巾送去快洗部，向洗完的第一天早晨连边（判断一下能不能在n天前洗完），流量为inf，费用为f
（5）每天晚上可以把脏餐巾送去慢洗部，向洗完的第一天早晨连边（判断一下能不能在n天前洗完），流量为inf，费用为s
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e4 + 10;
const int M = 5e5 + 10;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
struct Edge {
ll to, next, cap, flow, cost;
}edge[M];
ll head[N], tot, pre[N], n, m, s, t, ned[N];
ll minCost, maxFlow, dis[N];
bool vis[N];
void init() {
tot = 0;
memset(head, -1, sizeof(head));
}
void addedge(ll u, ll v, ll cap, ll cost) { //cap流量 cost花费
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].flow = 0;
edge[tot].next = head[u];
head[u] = tot++;
edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].cost = -cost;
edge[tot].flow = 0;
edge[tot].next = head[v];
head[v] = tot++;
}
bool spfa(ll s, ll t) {
queue<ll>q;
for(ll i = 0; i < N; ++i) {
dis[i] = inf;
vis[i] = 0;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = 1;
q.push(s);
while(!q.empty()) {
ll u = q.front();
q.pop();
vis[u] = 0;
for(ll i = head[u]; i != -1; i = edge[i].next) {
ll v = edge[i].to;
if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
if(pre[t] == -1) return 0;
else return 1;
}
ll MCMF(ll s, ll t) {
minCost = 0;
maxFlow = 0;
while(spfa(s, t)) {
ll minn = inf;
for(ll i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
if(minn > edge[i].cap - edge[i].flow)
minn = edge[i].cap - edge[i].flow;
}
for(ll i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
edge[i].flow += minn;
edge[i ^ 1].flow -= minn;
minCost += edge[i].cost * minn;
}
maxFlow += minn;
}
return maxFlow;
}
int main() {
init();
ll p, a, b, c, d;
scanf("%lld", &n);
s = 0, t = 2 * n + 1;
for(ll i = 1; i <= n; ++i) {///1~n晚上 n + 1~2 * n早上 s = 0 t = 2 * n + 1
scanf("%lld", &ned[i]);
addedge(s, i, ned[i], 0); ///每天晚上接受超级源点（每天早上）的脏餐巾
addedge(i + n, t, ned[i], 0);///每天早上需要干净的餐巾 连超级汇点
}
scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &c, &d);
for(int i = 2; i <= n; ++i) {
addedge(i - 1, i, inf, 0); ///前一天晚上的脏餐巾可以向后一天转移
int tmp = i - 1 + a;
if(tmp <= n)
addedge(i - 1, tmp + n, inf, b); ///脏餐巾慢洗 第i + b天后可以用
tmp = i - 1 + c;
if(tmp <= n)
addedge(i - 1, tmp + n, inf, d); ///脏餐巾快洗 第i + d天后可以用
}
for(int i = 1; i <= n; ++i)
addedge(s, i + n, inf, p); ///每天早上都可以购买新餐巾
MCMF(s, t);
printf("%lld\n", minCost);
return 0;
}
