网络流24题 P1251 餐巾计划问题 拆点

餐巾计划问题 拆点"/>

网络流24题 P1251 餐巾计划问题 拆点

题目描述

一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri​块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

我们知道，对于每一天，其实有两种状态：

    一天开始状态，这个时候应该决定买多少新的餐巾数目，有没有从洗衣部送过来的东西

    第一天结束，我们需要决定，是否需要对用过的餐巾进行封存，是否需要对把衣服送到两种洗衣部里面

那么很明显，一个点不能满足我们的需求，我们可以把点进行拆分，分成白天和晚上，对应有6种情况

  我们需要从起点连接每个白天，流量限制，费用为p，代表这个的餐巾选择新购买的数目

   从起点再连接每个点的晚上，流量限制为这一天所需的餐巾数目，代表这一天一定会产生这么多的用过的餐巾

   从每天早上连接到汇点流量限制为这一天所需的餐巾数目，代表这白天一定会消耗这么多餐巾

   由于可以把用过的餐巾存起来，我们把每个晚上的餐巾存到第二天从餐巾，流量为今天用的餐巾数目，费用为0

   我们可以把餐巾送到快洗部，那么应该这天晚上的餐巾，送到洗完的那一天的早上，流量上限是INF(因为可能有以前存的衣服)，费用为快洗部的费用

  也可以把餐巾送到慢洗部，那么应该这天晚上的餐巾，送到洗完的那一天的早上，流量上限是INF(因为可能有以前存的衣服)，费用为慢洗部的费用

  注意拆点的话，可以把点拆成i和i+n  

代码：

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<queue>
#define LL long long
using namespace std;
const LL N = 3e4+4,M = 4e6+7;
const LL INF = 0x3f3f3f3f;
LL ver[M],edge[M],cost[M],Next[M],head[N];
LL d[N],incf[N],pre[N],v[N],a[N];
LL n,k,tot,s,t,maxflow;
LL ans;
void add(LL x,LL y,LL z,LL c){ver[++tot]=y,edge[tot]=z,cost[tot]=c;Next[tot]=head[x],head[x]=tot;ver[++tot]=x,edge[tot]=0,cost[tot]=-c;Next[tot]=head[y],head[y]=tot;
}
bool spfa(){queue<LL>q;for (LL i=0;i<=N;i++){d[i]=INF;}memset(v,0,sizeof(v));q.push(s);d[s]=0;v[s]=1;incf[s]=INF;while(q.size()){LL x=q.front();v[x]=0;q.pop();for (int i=head[x];i;i=Next[i]){if(!edge[i])continue;int y=ver[i];if (d[y]>d[x]+cost[i] && edge[i]>0){d[y]=d[x]+cost[i];incf[y]=min(incf[x],edge[i]);pre[y]=i;if (!v[y])v[y]=1,q.push(y);}}}if (d[t]==INF)return false;return true;
}
void update(){int x=t;while(x!=s){int i=pre[x];edge[i]-=incf[t];edge[i^1]+=incf[t];x=ver[i^1];}maxflow+=incf[t];ans+=d[t]*incf[t];
}
int main(){LL q_day,q_w,s_day,s_w,p,maxflow=0;ans=0;tot=1;scanf("%lld",&n);s=2*n+2;t=2*n+3;for (LL i=1;i<=n;i++){scanf("%lld",&a[i]);}scanf("%lld%lld%lld%lld%lld",&p,&q_day,&q_w,&s_day,&s_w);for (LL i=1;i<=n;i++){add(s,i,INF,p);add(s,i+n,a[i],0);add(i,t,a[i],0);if (i<n)add(i+n,i+n+1,INF,0);if (i+q_day<=n){add(i+n,i+q_day,INF,q_w);}if (i+s_day<=n){add(i+n,i+s_day,INF,s_w);}}while(spfa())update();printf("%lld\n",ans);return 0;
}