【zkw费用流】[网络流24题]餐巾计划问题

时间:2021-03-15 05:40:20

题目描述

一个餐厅在相继的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。

输出格式:

输出文件共1行为最小的费用。

输入输出样例

输入样例#1:
3
3 2 4
10 1 6 2 3
输出样例#1:
64

题解

这题的建模真的不好想。。。

首先对于所有天数拆点,拆成X集合和Y集合

其中Xi表示第i天用完的餐巾,Yi表示第i天需要的餐巾

  从s到每个Xi连一条流量为Ri,花费为0的边,从每个Yi到t也连一条流量为Ri,花费为0的边

  从Xi到Xi+1连一条流量为inf,花费为0的边,表示Xi天多出没用的可以直接给Xi+1天

  从Xi到Yi+fast_time连一条流量为inf,花费为fast_cost的边,表示快洗

  从Xi到Yi+slow_time连一条流量为inf,花费为slow_cost的边,表示慢洗

之后跑zkw费用流就行

%%%zkw

代码

//by 减维
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<bitset>
#include<algorithm>
#define ll long long
#define maxn 4005
#define inf 1<<30
using namespace std; struct edge{
int to,ne,cap,val;
}e[maxn<<]; int n,s,t,ft,fc,st,sc,cost,ecnt=,head[maxn],dis[maxn];
ll ans;
bool pd[maxn],vis[maxn];
deque<int>q; void add(int x,int y,int z,int k){++ecnt;e[ecnt]=(edge){y,head[x],z,k};head[x]=ecnt;}
void addd(int x,int y,int z,int k){add(x,y,z,k);add(y,x,,-k);} bool bfs()
{
memset(pd,,sizeof(pd));
for(int i=;i<=t;++i)dis[i]=inf;
pd[t]=;dis[t]=;q.push_back(t);
while(!q.empty())
{
int d=q.front();q.pop_front();
pd[d]=;
for(int i=head[d];i;i=e[i].ne)
{
int dd=e[i].to;
if(e[i^].cap&&dis[dd]>dis[d]-e[i].val)
{
dis[dd]=dis[d]-e[i].val;
if(!pd[dd]){
pd[dd]=;
if(q.empty()||dis[dd]>dis[q.front()])q.push_back(dd);
else q.push_front(dd);
}
}
}
}
return dis[s]<inf;
} int dfs(int x,int cap)
{
vis[x]=;
if(x==t||cap==)return cap;
int tmp,ret=;
for(int i=head[x];i;i=e[i].ne)
{
int dd=e[i].to;
if((!vis[dd])&&e[i].cap&&dis[dd]==dis[x]-e[i].val)
{
tmp=dfs(dd,min(e[i].cap,cap));
cap-=tmp;ret+=tmp;
e[i].cap-=tmp;e[i^].cap+=tmp;
}
}
return ret;
} int main()
{
scanf("%d",&n);
s=,t=*n+;
for(int i=,x;i<=n;++i)
{
scanf("%d",&x);
addd(,i,x,);
addd(i+n,t,x,);
}
scanf("%d%d%d%d%d",&cost,&ft,&fc,&st,&sc);
for(int i=;i<=n;++i)
{
if(i+<=n)addd(i,i+,inf,);
if(i+ft<=n)addd(i,i+n+ft,inf,fc);
if(i+st<=n)addd(i,i+n+st,inf,sc);
addd(,i+n,inf,cost);
}
while(bfs())
{
vis[t]=;
while(vis[t])
{
memset(vis,,sizeof(vis));
int tmp=dfs(s,inf);
ans+=(ll)tmp*dis[s];
}
}
printf("%lld",ans);
return ;
}