【问题描述】
一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。
(1)购买新的餐巾，每块需p分；
(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
(3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<f)。
在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。
【输入】
输入文件共 3 行，第 1 行为总天数；第 2 行为每天所需的餐巾块数；第 3 行为每块餐巾的新购费用 p ，快洗所需天数 m ，快洗所需费用 f ，慢洗所需天数 n ，慢洗所需费用 s 。
【输出】
一行，最小的费用
【样例】
napkin.in
3
3 2 4
10 1 6 2 3
napkin.out
64
【数据规模】
n<=200,Ri<=50
虽然写完了，但是不太会解释。
题解出门左转hzwer神犇的博客
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
const int INF=1e9;
const int mxn=*;
inline int read(){
int sum=,flag=;char ch=getchar();
while(ch!='-'&&(ch>''||ch<''))ch=getchar();
if(ch=='-'){flag=-;ch=getchar();}
while(ch<=''&&ch>=''){sum=sum*+ch-'';ch=getchar();}
return sum*flag;
}
struct edge{
int u,v,nxt,f,w;
}e[mxn*mxn*];
int hd[mxn],mct=;
void add_edge(int u,int v,int c,int w){
e[++mct].u=u;e[mct].v=v;e[mct].nxt=hd[u];e[mct].f=c;e[mct].w=w;hd[u]=mct;return;
}
void insert(int u,int v,int c,int w){
add_edge(u,v,c,w);add_edge(v,u,,-w);return;
}
int N,p,n,m,S,T;
int a,f,s;
int dis[mxn];
int pre[mxn];
bool inq[mxn];
bool SPFA(){
memset(dis,0x3f,sizeof dis);
queue<int>q;
q.push(S);
dis[S]=;
while(!q.empty()){
int u=q.front();q.pop();inq[u]=;
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].v;
if(e[i].f> && dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
pre[v]=i;
if(!inq[v]){
inq[v]=;
q.push(v);
}
}
}
}
if(dis[T]!=0x3f3f3f3f)return ;
return ;
}
int solve(){
int tmp=0x3f3f3f3f,res=;
while(SPFA()){
tmp=0x3f3f3f3f;
for(int i=pre[T];i>;i=pre[e[i].u]){
tmp=min(tmp,e[i].f);
}
for(int i=pre[T];i>;i=pre[e[i].u]){
e[i].f-=tmp;
e[i^].f+=tmp;
res+=tmp*e[i].w;
}
}
return res;
}
int main(){
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
int i,j;
N=read();
S=;T=N*+;
for(i=;i<=N;i++){
a=read();
insert(S,i,a,);
insert(i+N,T,a,);
}
p=read();m=read();f=read();n=read();s=read();
for(i=;i<=N;i++){
if(i+<=N)insert(i,i+,INF,);
if(i+m<=N)insert(i,i+m+N,INF,f);
if(i+n<=N)insert(i,i+n+N,INF,s);
insert(S,i+N,INF,p);//购买
}
int ans=solve();
printf("%d\n",ans);
return ;
}