BZOJ1221/HNOI2001软件开发

Posted on By 二价氢

我们可以像下面这样建图

这里是原图的矢量图

下面是对图的解释

  1. 把每天拆成两个点(图中蓝色正方形)和(图中红色圆形)分别表示第i天要用的毛巾和用过的毛巾。
  2. 源点到所有连一条容量为该天需用毛巾数,费用为f的边,表示新买毛巾。(橙色边)
  3. 所有到汇点连一条容量为该天需用毛巾数,费用为0的边,表示每天都必须用足够的毛巾。(紫色边)
  4. 然后每天会产生若干用过的毛巾,所以再从向所有的 连边,容量同样是该天需用毛巾数,费用为0。(青色边)
  5. 这样,对某天用完后的毛巾进行消毒就对应了的边:
  6. A方式 :从每个连边,容量为无穷,费用为fA(蓝色边)
  7. B方式 :从每个连边,容量为无穷,费用为fB(绿色边)
  8. 然后每天用过的毛巾可以拖延到下一天再送去消毒,所以每个连边,容量为无穷,费用为0。(红色边)

最后求最小费用最大流即可

AC-Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=2010,MAXM=100005;
//--Graph
const int S=2004,T=2005,INF=99999999;
struct Edge{int t,v,c,op,next;}E[MAXM];
int pFirst[MAXN],totE;
int Dis[MAXN],Pre[MAXN],NEd[MAXN];
bool inQ[MAXN];
//--Problem
int n,a,b,f,fA,fB;
void AddEdge(int s,int t,int v,int c)
{
    int E1=++totE,E2=++totE;
    E[E1].t=t;E[E1].v=v;E[E1].c= c;E[E1].op=E2;E[E1].next=pFirst[s];
    pFirst[s]=E1;
    E[E2].t=s;E[E2].v=0;E[E2].c=-c;E[E2].op=E1;E[E2].next=pFirst[t];
    pFirst[t]=E2;
}
inline int X(int i)
{
    return i*2-1;
}
inline int Y(int i)
{
    return i*2;
}
bool Spfa()
{
    memset(Dis,0x3f,sizeof(Dis));
    memset(Pre,-1,sizeof(Pre));
    memset(NEd,-1,sizeof(NEd));
    memset(inQ,0,sizeof(inQ));
    queue <int> Q;
    Q.push(S);
    Dis[S]=0;
    int u,v;
    while (!Q.empty())
    {
        u=Q.front();Q.pop();
        inQ[u]=false;
        for (int p=pFirst[u];p;p=E[p].next)
        {
            v=E[p].t;
            if (E[p].v>0)
                if (Dis[v]>Dis[u]+E[p].c)
                {
                    Dis[v]=Dis[u]+E[p].c;
                    Pre[v]=u;NEd[v]=p;
                    if (!inQ[v])
                    {
                        inQ[v]=true;
                        Q.push(v);
                    }
                }
        }
    }
    return (Pre[T]!=-1);
}
int MinCostMaxFlow()
{
    int u;
    int Cost=0,tmpflow;
    while (Spfa())
    {
        tmpflow=INF;
        for (u=T;Pre[u]!=-1;u=Pre[u])
            tmpflow=min(tmpflow,E[NEd[u]].v);
        for (u=T;Pre[u]!=-1;u=Pre[u])
        {
            E[NEd[u]].v-=tmpflow;
            E[E[NEd[u]].op].v+=tmpflow;
            Cost+=tmpflow*E[NEd[u]].c;
        }
    }
    return Cost;
}
int main()
{
    int tmp;
    scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fA,&fB);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&tmp);
        AddEdge(S,X(i),tmp,f);
        AddEdge(X(i),T,tmp,0);
        AddEdge(S,Y(i),tmp,0);
        if (i<n)
            AddEdge(Y(i),Y(i+1),INF,0);
        if (i+a+1<=n)
            AddEdge(Y(i),X(i+a+1),INF,fA);
        if (i+b+1<=n)
            AddEdge(Y(i),X(i+b+1),INF,fB);
    }
    printf("%d\n",MinCostMaxFlow());
    return 0;
}