一个餐厅在相继的 N 天里,每天需用餐巾。假设第 i天需要 A[i]块餐巾( i=1,2,...,N)。
餐厅可以购买新的餐巾,每块餐巾的费用为 p 分;
或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分; 或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。
注意每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。
将每天当作一个点，而且拆点（上午和晚上)，然后连边
#include<iostream>
#include<queue>
#include<cstring>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
const int N =1e5, M=1e5+100;
#define int long long
#define inf 1e9
int all=1,hd[N],go[M],w[M],nxt[M],cost[M];
int S,T,n,m;
int pre[N],mn[N],dis[N],vis[N],ans=0;
void add_(int x,int y,int z,int c){
nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
w[all]=z; cost[all]=c;
swap(x,y);
nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
w[all]=0; cost[all]= -c;
}
bool spfa(){
int i;
queue<int> q;
q.push(S);
for(i=0;i<N;i++) dis[i]=inf;
for(i=1;i<N;i++) vis[i]=0;
mn[S]=inf, dis[S]=0, vis[S]=1;
while(!q.empty()){
int x=q.front();
vis[x]=0;
q.pop();
for(i=hd[x];i;i=nxt[i]){
int y=go[i],z=w[i],c=cost[i];
if(w[i]==0) continue;
if(dis[x]+c<dis[y]){
dis[y]=dis[x]+c;
mn[y]=min(mn[x],z);
pre[y]=i;
if(vis[y]==0) vis[y]=1,q.push(y);
}
}
}
if(dis[T]==inf) return 0; return 1;
}
void solve(){
int maxf=0, minc=0;
while(spfa()){
int x= T;
maxf+= mn[T] ,minc+= mn[T]*dis[T];
while(x!=S){
int i=pre[x];
w[i]-= mn[T];
w[i^1]+=mn[T];
x=go[i^1];
}
}
cout<<minc<<endl;
}
int T1,M1,T2,M2;
signed main(){
int i,x;
cin>>n; S=0,T=2*n+1;
for(i=1;i<=n;i++){
cin>>x; add_(S,i,x,0); add_(i+n,T,x,0);
}
cin>>m>>T1>>M1>>T2>>M2;
for(i=1;i<=n;i++){
if(i+1<=n) add_(i,i+1,inf,0);
if(i+T1<=n) add_(i,i+n+T1,inf,M1);
if(i+T2<=n) add_(i,i+n+T2,inf,M2);
add_(S,i+n,inf,m);
}
solve();
}