网络流24题之餐巾计划问题

题面

一道不好想的网络流题。

似乎可以上下界费用流？

大概是这样的：

建一个源点一个汇点，然后对于n天，各建两个点$D_i,C_i$表示脏餐巾和干净餐巾。

（这里用$(flow,cost)$来表示边的最大流量flow，费用为cost）

首先$C_i$向t连$(r_i,0)$的边，表示使用$r_i$块干净餐巾。

对应着s向$D_i$连$(r_i,0)$的边，表示得到了$r_i$块脏餐巾。

s向$C_i$连$(r_i,p)$的边，表示买新餐巾。

$D_i$向$C_{i+m}$连$(+\infty,f)$的边，表示快洗餐巾。

向$C_{i+n}$连$(+\infty,s)$的边，表示慢洗。

$D_i$向$D_{i+1}$连$(+\infty,0)$的边，表示保存脏餐巾，过些天再洗。

跑费用流即可。

/*
Author: CNYALI_LK
LANG: C++
PROG: 1251.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
    ll cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
    putchar(end);
}
ll dirty[102424],clean[102424],t,s;
ll r[102424],p,tq,cq,ts,cs;
struct MCF{
    ll to[102424],lst[102424],w[102424],c[102424],beg[102424],e,n;
    ll mincost,dis[102424],pre[102424],flow[102424];
    MCF(){
        e=1;
    }
    void add(ll u,ll v,ll flow,ll cost){
        to[++e]=v;
        lst[e]=beg[u];
        beg[u]=e;
        w[e]=flow;
        c[e]=cost;
        to[++e]=u;
        lst[e]=beg[v];
        beg[v]=e;
        w[e]=0;
        c[e]=-cost;
    }
    ll q[1204848],*l,*r,inq[102424];
    ll spfa(ll s,ll t){
        for(ll i=1;i<=n;++i)dis[i]=0x3f3f3f3f3f3f3f3f,pre[i]=-1,flow[i]=0;
        *(l=r=q)=s;
        dis[s]=0;
        pre[s]=0;
        inq[s]=1;
        flow[s]=0x3f3f3f3f3f3f3f3f;
        while(l<=r){
            for(ll i=beg[*l];i;i=lst[i])if(w[i]&&chkmin(dis[to[i]],dis[*l]+c[i])){
                pre[to[i]]=i^1;
                flow[to[i]]=min(flow[*l],w[i]);
                if(!inq[to[i]]){
                    inq[*(++r)=to[i]]=1;
                }
            }
            inq[*l]=0;
            ++l;
        }
        
        if(!flow[t])return 0;
        ll h=t,i;
        while(pre[h]){
            i=pre[h];
            w[i]+=flow[t];
            w[i^1]-=flow[t];
            mincost+=c[i^1]*flow[t];
            h=to[i];
        }
        return 1;
    }
    ll solve(ll s,ll t){
        mincost=0;
        while(spfa(s,t));
        return mincost;
    }
};
MCF Min_Cost_Flow;
int main(){
#ifdef cnyali_lk
    freopen("1251.in","r",stdin);
    freopen("1251.out","w",stdout);
#endif
    ll n;
    n=read();
    s=1;
    t=(n+1)<<1;
    Min_Cost_Flow.n=t;
    for(ll i=1;i<=n;++i)dirty[i]=i<<1,clean[i]=i<<1|1;
    for(ll i=1;i<=n;++i){
        r[i]=read();
    }
    p=read();tq=read();cq=read();ts=read();cs=read();
    for(ll i=1;i<=n;++i){
        Min_Cost_Flow.add(s,dirty[i],r[i],0);
        Min_Cost_Flow.add(s,clean[i],r[i],p);
        Min_Cost_Flow.add(clean[i],t,r[i],0);
        Min_Cost_Flow.add(dirty[i],dirty[i+1],0x3f3f3f3f3f3f3f3f,0);
        Min_Cost_Flow.add(dirty[i],clean[i+tq],0x3f3f3f3f3f3f3f3f,cq);
        Min_Cost_Flow.add(dirty[i],clean[i+ts],0x3f3f3f3f3f3f3f3f,cs);
    }
    printf("%lld\n",Min_Cost_Flow.solve(s,t));
    return 0;
}