(color{#0066ff}{题目描述})
一个餐厅在相继的 N 天里,每天需用的餐巾数不尽相同。假设第 i 天需要 (r_i) 块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 p 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 n 天((n>m)),其费用为 s 分((s<f))。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
(color{#0066ff}{输入格式})
由标准输入提供输入数据。文件第 1 行有 1 个正整数 N，代表要安排餐巾使用计划的天数。
接下来的 N 行是餐厅在相继的 N 天里,每天需用的餐巾数。
最后一行包含5个正整数(p,m,f,n,s)。(p) 是每块新餐巾的费用; (m) 是快洗部洗一块餐巾需用天数; (f) 是快洗部洗一块餐巾需要的费用; (n) 是慢洗部洗一块餐巾需用天数; (s) 是慢洗部洗一块餐巾需要的费用。
(color{#0066ff}{输出格式})
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
(color{#0066ff}{输入样例})
3
1 7 5
11 2 2 3 1
(color{#0066ff}{输出样例})
134
(color{#0066ff}{数据范围与提示})
(N leq 2000)
(ri leq 10000000)
(p,f,s leq 10000)
(时限4s)
(color{#0066ff}{题解})
这是一道费用流
首先，拆点
把每天拆成早上晚上
每天晚上会收到脏餐巾，其中一个来源就是当天用的干净的餐巾
这个来源是固定的，我们通过输入可以得知
所以可以理解为从源点获得
每天早上，我们会获得干净的餐巾，同样，有很多来源
下面开始建图
1、从S向每一天晚上连容量为当天需求，权值为0的边，代表从当天早上获得的脏餐巾
2、从每一天早上向T连一条容量为当天需求，权值为0的边，代表当天要供给这么多餐巾（干净的），流满了就代表当天够用，当然最大流一定会让它流满
3、每天晚上向第二天晚上连一条容量为inf，权值为0的边，代表将本日的脏餐巾留到第二天（不能是早上，因为早上只能用干净的餐巾）
4、每天晚上向当天+慢洗店所用天数（注意边界）的那天早上，连容量为inf，边权为慢洗店单价的边，表示当天送一些脏餐巾到慢洗店，在洗完后回到那天早上（变干净了）
5、同上
6、从起点向每天早上连容量为inf，边权为餐巾单价的边，代表可以买新餐巾
一边mcmf就行了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define _ 0
#define LL long long
inline LL in()
{
LL x=0,f=1; char ch;
while(!isdigit(ch=getchar()))(ch=='-')&&(f=-f);
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
struct node
{
int to;
LL can,dis;
node *nxt,*rev;
node(int to=0,LL can=0,LL dis=0,node *nxt=NULL):to(to),can(can),dis(dis),nxt(nxt){}
void *operator new (size_t)
{
static node *S=NULL,*T=NULL;
return (S==T&&(T=(S=new node[1024])+1024)),S++;
}
};
const LL inf=999999999999999LL;
typedef node* nod;
nod head[50505],road[50505];
LL dis[50505],change[50505];
bool vis[50505];
LL need[50505];
LL aa,bb,cc,dd,ee;
int n,s,t;
std::queue<int> q;
inline void add(int from,int to,LL dis,LL can)
{
nod o=new node(to,can,dis,head[from]);
head[from]=o;
}
inline void link(int from,int to,LL dis,LL can)
{
add(from,to,dis,can);
add(to,from,-dis,0);
head[from]->rev=head[to];
head[to]->rev=head[from];
}
inline bool spfa()
{
for(int i=s;i<=t;i++) dis[i]=change[i]=inf,vis[i]=0;
dis[s]=0;
q.push(s);
while(!q.empty())
{
int tp=q.front(); q.pop();
vis[tp]=false;
for(nod i=head[tp];i;i=i->nxt)
{
if(dis[i->to]>dis[tp]+i->dis&&i->can>0)
{
dis[i->to]=dis[tp]+i->dis;
road[i->to]=i;
change[i->to]=std::min(change[tp],i->can);
if(!vis[i->to]) vis[i->to]=true,q.push(i->to);
}
}
}
return change[t]!=inf;
}
inline void mcmf()
{
LL cost=0;
while(spfa())
{
cost+=change[t]*dis[t];
for(int i=t;i!=s;i=road[i]->rev->to)
{
road[i]->can-=change[t];
road[i]->rev->can+=change[t];
}
}
printf("%lld",cost);
}
int main()
{
n=in();
s=0,t=(n<<1)+1;
for(int i=1;i<=n;i++) need[i]=in();
aa=in(),bb=in(),cc=in(),dd=in(),ee=in();
for(int i=1;i<=n;i++)
{
link(s,i+n,aa,inf);
link(s,i,0,need[i]);
link(i+n,t,0,need[i]);
if(i!=n) link(i,i+1,0,inf);
if(i+bb<=n) link(i,i+n+bb,cc,inf);
if(i+dd<=n) link(i,i+n+dd,ee,inf);
}
mcmf();
return 0;
}