题解报告——软件开发

题目描述

某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。

你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

输入输出格式

输入格式：

第1行为n,a,b,f,fA,fB.

第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）

输出格式：

最少费用

输入输出样例

输入样例#1： 复制

4  1  2  3  2  1                         
8  2  1  6

输出样例#1： 复制

【思路分析】
首先看到这道题时，“这不就是一个线性DP吗？？！！”，然后果断开码，写了一半发现，哎呀！这转移方程咋个奇奇妙妙的啊？貌似我的DP GG了，只有去看题解。。。
本以为可以看到很妙妙的DP操作，结果映入眼帘的TM是“费用流？？！！”仿佛命运给我开了个大大的玩笑，太假了。。。
好嘛那么就来看看我们这道题咋个建图吧。。。

拆点，将每个点拆成入点和出点，表示为i和i+n；
考虑最后每天都有且只有ni个餐巾，所以建立源点S和汇点T，并在S和i之间连容量为INF、费用为0的边，

同理在i+n和T之间连容量为INF、费用为0的边。

考虑几个方案：对于a和b，只要在i天和i+a天之间连一条容量为INF、费用为fa的边，b同理；
考虑一天的餐巾可以原封不动的留到明天，故可以在i和i+1之间连一条容量为INF，费用为0的边；
最后为了保证每天能有足够的餐巾（每条汇弧饱和），可以在S在每个i+n之间加一条容量为INF、费用为f的边；

最后简单地跑一遍费用流即可；

【代码实现】

#include<cstdio>
#include<cctype>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
void read(int &v)
{
    int f;char ch;
    while(!isdigit(ch=getchar())&&ch!='-'); ch=='-'?(f=-1,v=0):(f=1,v=ch-'0');
    while(isdigit(ch=getchar())) v=v*10+ch-'0';v=v*f;
}
const int N=2e3+5,INF=1e9+7;
struct sd{
    int next,to,w,exp;
    sd(){};
    sd(int a,int b,int c,int d){next=a,to=b,w=c,exp=d;}
}edge[N*100];
queue<int> que;
int head[N],pre[N],last[N],dis[N],flow[N],n,A,B,f,fa,fb,cnt=1,s,t;
bool vis[N];
ll ans;
void add_edge(int from,int to,int w,int exp)
{
    edge[++cnt]=sd(head[from],to,w,exp),head[from]=cnt;
    edge[++cnt]=sd(head[to],from,0,-exp),head[to]=cnt;
}
bool spfa()
{
    memset(dis,127,sizeof(dis));
    memset(flow,127,sizeof(flow));
    pre[t]=-1,dis[s]=0,vis[s]=1,que.push(s);
    while(!que.empty())
    {
        int v=que.front();que.pop(),vis[v]=0;
        for(int i=head[v];i;i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]>dis[v]+edge[i].exp&&edge[i].w>0)
            {
                dis[to]=dis[v]+edge[i].exp;
                last[to]=i,pre[to]=v;
                flow[to]=min(flow[v],edge[i].w);
                if(!vis[to]) que.push(to),vis[to]=1;
            }
        }
    }
    return pre[t]!=-1;
}
int main()
{
    read(n),read(A),read(B),read(f),read(fa),read(fb);
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++)
    {
        int nn;read(nn);
        add_edge(s,i,nn,0),add_edge(i+n,t,nn,0);
        add_edge(s,i+n,INF,f);
        if(i+A+1<=n) add_edge(i,i+A+1+n,INF,fa);
        if(i+B+1<=n) add_edge(i,i+B+1+n,INF,fb);
        if(i!=n) add_edge(i,i+1,INF,0);
    }
    while(spfa())
    {
        int id=t;
        ans+=1ll*dis[t]*flow[t];
        while(id!=s)
        {
            edge[last[id]].w-=flow[t];
            edge[last[id]^1].w+=flow[t];
            id=pre[id];
        }
    }
    printf("%lld",ans);
    return 0;
}