洛谷P1251 餐巾计划问题

题目大意：

一个餐馆每条都要\(r_i\)条干净毛巾

获得干净毛巾的来源有以下几个：

1.买买买，需要\(a\)元

2.脏毛巾快洗，需要\(f\)天，\(n\)元

3.脏毛巾慢洗，需要\(s\)天，\(m\)元

一开始是没有毛巾的，求怎么样安排才能让每天都干净毛巾数量达到要求且花费最少

构造最大流跑费用流

我们可以把每天拆为早上和晚上两个点，其中每天早上对\(T\)连接一个容量为\(r_i\)，花费为\(0\)的边，使得最大流等于毛巾需要的数量

然后构造花费方案

首先我们可以直接购买干净毛巾，\(S\)向每天早上直接连容量为\(inf\)，花费为\(a\)的边

每天我们可以获得\(r_i\)个脏毛巾，所以每天晚上对\(T\)连一个容量为\(r_i\)，花费为\(0\)

然后是处理洗毛巾，每天晚上对\(f_i\)和\(s_i\)天后的早上分别连边，容量为\(inf\)，花费为\(n_i\)和\(m_i\)

干净毛巾和脏毛巾不需要的可以传递给下一天早上

然后一道构造题（雾）就解决了

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') f=0,ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
const int inf=0x3f3f3f3f3f3f3f3f;
int n,st,ed;
int ret;
int r[8010];
int newpaper,fast,fastcost,slow,slowcost;
int head[8010],cnt=1;
int dis[8010],c[8010];
int pre[8010],eg[8010];
bool vis[8010];
struct point
{
    int nxt,to,val,c;
}a[200010];
inline void add(int x,int y,int c,int val)
{
    a[++cnt].nxt=head[x];
    a[cnt].to=y;
    a[cnt].c=c;
    a[cnt].val=val;
    head[x]=cnt;
}
queue<int> q;
inline bool spfa()
{
    memset(c,0x3f,sizeof(c));
    memset(dis,0x3f,sizeof(dis));dis[st]=0;
    memset(vis,0,sizeof(vis));vis[st]=1;
    q.push(st);pre[ed]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=a[i].nxt)
        {
            int t=a[i].to;
            if(a[i].c&&dis[t]>dis[now]+a[i].val)
            {
                pre[t]=now;
                eg[t]=i;
                dis[t]=dis[now]+a[i].val;
                c[t]=min(c[now],a[i].c);
                if(!vis[t])
                {
                    vis[t]=1;
                    q.push(t);
                }
            }
        }
    }
    return pre[ed];
}
inline void dinic()
{
    while(spfa())
    {
        ret+=c[ed]*dis[ed];
        int now=ed;
        while(now!=st)
        {
            a[eg[now]].c-=c[ed];
            a[eg[now]^1].c+=c[ed];
            now=pre[now];
        }
    }
}
signed main()
{
    n=read();
    st=7777,ed=7778;
    for(int i=1;i<=n;++i) r[i]=read();

    newpaper=read(),fast=read(),fastcost=read(),slow=read(),slowcost=read();

    for(int i=1;i<=n;++i)
    {

        add(st,i+3000,inf,newpaper),add(i+3000,st,0,-newpaper);//买干净毛巾

        add(st,i,r[i],0),add(i,st,0,0);//获得脏毛巾，注意获得脏毛巾不需要花费价值

        add(i+3000,ed,r[i],0),add(ed,i+3000,0,0);//每天需要的干净毛巾

        if(i!=n) add(i+3000,i+3001,inf,0),add(i+3001,i+3000,0,0);//干净/脏毛巾传递

        if(i+fast<=n) add(i,i+fast+3000,inf,fastcost),add(i+fast+3000,i,0,-fastcost);//快洗
        if(i+slow<=n) add(i,i+slow+3000,inf,slowcost),add(i+slow+3000,i,0,-slowcost);//慢洗
    }
    dinic();
    printf("%lld\n",ret);//费用流
return 0;
}