餐巾计划问题

题目描述
一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 i 天需要 ri 块餐巾( i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 p 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 n 天(n>m),其费用为 s 分(s<f)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

输入格式
由标准输入提供输入数据。文件有 1 个正整数 N，代表要安排餐巾使用计划的天数。

接下来的 N 行是餐厅在相继的 N 天里,每天需用的餐巾数。

最后一行包含5个正整数p,m,f,n,s。p 是每块新餐巾的费用; m 是快洗部洗一块餐巾需用天数; f是快洗部洗一块餐巾需要的费用; n 是慢洗部洗一块餐巾需用天数; s 是慢洗部洗一块餐巾需要的费用。

输出格式
将餐厅在相继的 N 天里使用餐巾的最小总花费输出

输入输出样例
输入 #1 复制
3
1 7 5
11 2 2 3 1

输出 #1 复制
134

说明/提示
N<=2000

ri<=10000000

p,f,s<=10000

时限4s

作为网络流24题中的一题，与其他让我们练手速的网络流24题，这道题还是很考验建图功底的。

看到题目，不难想到是费用流，主要就是怎么建图。

因为一天分为两个阶段，拿到干净的餐巾和把脏的餐巾送去洗两个阶段，所以我们可以把一天分为两个阶段，也就是拆点，把一个点拆成两个点，分别表示早上和晚上。

对于每一个操作我们可以这样分析：

建立源点S，表示我们每天的脏的餐巾流向洗的阶段；建立汇点T，表示我们往汇点送干净的餐巾。

我们每天可以购买新的餐巾，那么连一条s到每天早上的边，流量为inf，费用为买餐巾的费用。
我们每天晚上可以把餐巾送到快洗，那么连一条i天晚上到i+time天早上的边，流量为inf，费用为快洗的费用。
我们每天晚上可以把餐巾送到慢洗，那么连一条i天晚上到i+time天早上的边，流量为inf，费用为慢洗的费用。
我们每天可以不把脏餐巾洗完，留到第二天，那么连一条i天晚上到i+1天晚上的边，流量为inf，费用为0。

最后跑一遍最下费用流即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010,M=1e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,s,t,a,b,c,d,e,dst[N],v[N],ei[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(dst,0x3f,sizeof dst);	queue<int> q;	q.push(s);	dst[s]=0;
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&dst[to[i]]>dst[u]+w[i]){
				dst[to[i]]=dst[u]+w[i];
				v[to[i]]=u;	ei[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return dst[t]!=inf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[ei[i]]);
		for(int i=t;i!=s;i=v[i])	flow[ei[i]]-=mi,flow[ei[i]^1]+=mi;
		res+=mi*dst[t];
	}
	return res;
}
signed main(){
	cin>>n;	s=0;	t=2*n+2;
	for(int i=1;i<=n;i++){
		int x;	cin>>x;	add(i+n,t,x,0);	add(s,i,x,0);
	}
	cin>>a>>b>>c>>d>>e;
	for(int i=1;i<=n;i++){
		add(s,i+n,inf,a);	
		if(i+1<=n)	add(i,i+1,inf,0);
		if(i+b<=n)	add(i,i+b+n,inf,c);
		if(i+d<=n)	add(i,i+d+n,inf,e);
	}
	cout<<EK()<<endl;
	return 0;
}