网络流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; }
