题目描述
一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn天(n>mn>m),其费用为 ss 分(s<fs<f)。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入输出格式
输入格式：
由标准输入提供输入数据。文件第 1 行有 1 个正整数 NN，代表要安排餐巾使用计划的天数。
接下来的 NN 行是餐厅在相继的 NN 天里,每天需用的餐巾数。
最后一行包含5个正整数p,m,f,n,sp,m,f,n,s。pp 是每块新餐巾的费用; mm 是快洗部洗一块餐巾需用天数; ff 是快洗部洗一块餐巾需要的费用; nn 是慢洗部洗一块餐巾需用天数; ss 是慢洗部洗一块餐巾需要的费用。
输出格式
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
解题思路：
考虑一下流量问题，发现最大流已经确定了。
此时需要构造一个流使每天的流量都满足要求，
那么就应该在汇点附近约束。
所以需要让每天的餐巾指向汇点。
需要满足直接购买，所以连入新流通入餐巾流中。
考虑餐巾的来源还有洗，那么在前几天的废餐巾指向这个新餐巾。
而废餐巾每天的数量都是固定的，所以连源上就好了。
考虑到可能有余负，向下一天的餐巾连边
建图都讲了边权就不说了。
最后跑一遍费用流就好了。
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
const lnt oo=0x3f3f3f3f3f3f3f3fll;
struct pnt{
int hd;
int pre;
int lst;
lnt val;
lnt dis;
bool vis;
}p[];
struct ent{
int twd;
int lst;
lnt vls;
lnt dis;
}e[];
int cnt;
int n,m;
int s,t;
int P,M,F,N,S;
std::queue<int>Q;
void ade(int f,int t,lnt v,lnt d)
{
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].dis=d;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
bool Spfa(void)
{
while(!Q.empty())Q.pop();
for(int i=;i<=t;i++)
{
p[i].dis=p[i].val=oo;
p[i].vis=false;
}
p[s].dis=;
p[s].vis=true;
p[t].pre=-;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();
Q.pop();
p[x].vis=false;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].dis>p[x].dis+e[i].dis&&e[i].vls>)
{
p[to].dis=p[x].dis+e[i].dis;
p[to].pre=x;
p[to].val=std::min(p[x].val,e[i].vls);
p[to].lst=i;
if(p[to].vis)continue;
p[to].vis=true;
Q.push(to);
}
}
}
return p[t].pre!=-;
}
lnt Ek(void)
{
lnt ans=;
while(Spfa())
{
ans+=p[t].dis*p[t].val;
for(int i=t;i!=s;i=p[i].pre)
{
e[p[i].lst].vls-=p[t].val;
e[((p[i].lst-)^)+].vls+=p[t].val;
}
}
return ans;
}
int main()
{
// freopen("a.in","r",stdin);
scanf("%d",&n);
s=n*+;
t=s+;
for(int i=;i<=n;i++)
{
int v;
scanf("%d",&v);
ade(i,t,v,);
ade(t,i,,);
ade(s,i+n,v,);
ade(i+n,s,,);
}
scanf("%d%d%d%d%d",&P,&M,&F,&N,&S);
for(int i=;i<=n;i++)
{
ade(s,i,oo,P);
ade(i,s,,-P);
if(i+M<=n)
{
ade(i+n,i+M,oo,F);
ade(i+M,i+n,,-F);
}
if(i+N<=n)
{
ade(i+n,i+N,oo,S);
ade(i+N,i+n,,-S);
}
if(i+<=n)
{
ade(i,i+,oo,);
ade(i+,i,,);
}
}
printf("%lld\n",Ek());
return ;
}