P2223 [HNOI2001]软件开发

· · 题解

本文会具体地对建模进行讲解和分析。

算法

最小费用最大流

建模

因为每天使用的毛巾是固定的，我们不需要去关心这个部分。显然，我们的任务就是处理每天晚上使用过的毛巾和给每天早上提供毛巾。而网络的流就相当于毛巾从源点产生，经过网络之后给汇点提供新毛巾。源点产生的毛巾可以是旧的或新的，接下来会详细讲解。

很容易想到拆点的思想，将每天拆成早上和晚上，分别进行处理。本文中设第i天的早上和晚上的节点编号分别为i和i+n。

  1. 每天晚上从源点获得当天使用过的旧毛巾，不需要费用，第i天的数量为n_i，即从源点s向i+n(i\in[1,n])连一条流量为n_i，费用为0的边。
  2. 每天早上向汇点提供当天需要的新毛巾，不需要费用，第i天的数量为n_i，即从i(i\in[1,n])向汇点t连一条流量为n_i，费用为0的边。
  3. 每天早上可以从汇点购买毛巾，单位费用为f，数量不限，即从源点s向i(i\in[1,n])连一条流量为inf，费用为f的边。
  4. 每天晚上可以把旧毛巾送去以A方式进行消毒，单位费用为f_a，数量不限，需要到a天后的早上才可以使用。注意，这里的a天是指全天，即若第1天晚上送毛巾去消毒，消毒需要1天，要到第3天早上才可以用。同时要注意边界问题，不能超出n天的范围。即从i+n(i\in[1,n-a-1])向i+a+1连一条流量为inf，费用为f_a的边。
  5. 同理，每天晚上还可以把旧毛巾送去以B方式进行消毒，单位费用是f_b，数量不限，即从i+n(i\in[1,n-b-1])向i+b+1连一条流量为inf，费用为f_b的边。
  6. 每一天晚上还可以选择不处理部分毛巾，把毛巾留到第二天晚上，不需要费用。这里有几点要说明，第一，因为旧毛巾不能使用，所以要留到第二天晚上而不是早上；第二，虽然根据贪心的思想是越早消毒越好，但实际上有可能消毒了却不需要用的情况出现，因此可以将旧毛巾留到第二天晚上。实际上也可以从每一条早上向第二天早上连边，表示将新毛巾留到第二天早上使用，也是同样的道理，都可行。这个操作也要注意边界问题。即从i+n(i\in[1,n-1])向i+1+n连一条流量为inf，费用为0的边。

以上就是全部的建模，建模之后求最小费用最大流即可。

最后给出代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ano ((i-1)^1)+1
using namespace std;
const int INF=0x7f7f7f7f,N=2e3+100,M=6e3+100;
int n,a,b,f,fa,fb,tot,ans,s,t;
int head[N],ver[2*M],edge[2*M],Next[2*M],cost[2*M];
int pre[N],minf[N],d[N];
bool v[N];
void add(int x,int y,int z,int 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()
{
    memset(v,0,sizeof(v));
    memset(d,0x7f,sizeof(d));
    queue<int> q;
    d[s]=0,v[s]=1,minf[s]=INF;
    q.push(s);
    while(q.size())
    {
        int x=q.front();q.pop();v[x]=0;
        for(int i=head[x];i;i=Next[i])
            if(edge[i])
            {
                int y=ver[i];
                if(d[x]+cost[i]<d[y])
                {
                    d[y]=d[x]+cost[i];
                    minf[y]=min(minf[x],edge[i]);
                    pre[y]=i;
                    if(!v[y])
                    {
                        q.push(y);
                        v[y]=1;
                    }
                }
            }
    }
    return d[t]!=INF;
}
void update()
{
    int x=t;
    while(x!=s)
    {
        int i=pre[x];
        edge[i]-=minf[t];
        edge[ano]+=minf[t];
        x=ver[ano];
    }
    ans+=d[t]*minf[t];
}//最小费用最大流模板
int main()
{
    scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
    t=2*n+1,a++,b++;//也可以先将a,b分别加1，后面就不用加1
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add(s,i+n,x,0),add(i,t,x,0),add(s,i,INF,f);//1,2,3操作
        if(i+a<=n)
            add(i+n,i+a,INF,fa);//4操作
        if(i+b<=n)
            add(i+n,i+b,INF,fb);//5操作
        if(i+1<=n)
            add(i,i+1,INF,0);//6操作，这里是从每天早上向第二天早上连边
    }
    while(spfa())
        update();//跑最小费用最大流。
    printf("%d",ans);
    return 0;
}