bzoj1221

题解：

费用流

构图才是难点

代码：

#include<bits/stdc++.h>
const int N=2005,T=2001;
using namespace std;
int x,cnt=1,day,p,m,f,n,s,ans,from[N],q[N],dis[N],head[N],inq[N];
struct data{int from,to,next,v,c;}e[N*N];
void ins(int u,int v,int w,int c)
{
    cnt++;
    e[cnt].from=u;e[cnt].to=v;
    e[cnt].v=w;e[cnt].c=c;
    e[cnt].next=head[u];head[u]=cnt;
}
void jb(int u,int v,int w,int c)
{
    ins(u,v,w,c);
    ins(v,u,0,-c);
}
int spfa()
{
    for (int i=0;i<=T;i++)dis[i]=1e9;
    int t=0,w=1,i,now;
    dis[0]=q[0]=0;inq[0]=1;
    while (t!=w)
     {
        now=q[t];t++;
        if (t==2001)t=0;
        for (int i=head[now];i;i=e[i].next)
         {
            if (e[i].v&&dis[e[i].to]>dis[now]+e[i].c)
             {
                from[e[i].to]=i;
                dis[e[i].to]=dis[now]+e[i].c;
                if (!inq[e[i].to])
                 {
                    inq[e[i].to]=1;
                    q[w++]=e[i].to;
                    if (w==2001)w=0;
                 }
             }
         }
        inq[now]=0;
     }
    if (dis[T]==1e9)return 0;
    return 1;
}
void mcf()
{
    int x=1e9;
    for (int i=from[T];i;i=from[e[i].from])x=min(e[i].v,x);
    for (int i=from[T];i;i=from[e[i].from]) 
     {
        e[i].v-=x;
        e[i^1].v+=x;
        ans+=x*e[i].c;
     }
}
int main()
{
    scanf("%d%d%d%d%d%d",&day,&m,&n,&p,&f,&s);
    for (int i=1;i<=day;i++)
     {
        if (i+1<=day)jb(i,i+1,1e9,0);
        if (i+m+1<=day)jb(i,day+i+m+1,1e9,f);
        if (i+n+1<=day)jb(i,day+i+n+1,1e9,s);
        jb(0,day+i,1e9,p);
     }
    for (int i=1;i<=day;i++)
     {
        scanf("%d",&x);
        jb(0,i,x,0);
        jb(day+i,T,x,0);
     }
    while (spfa())mcf();
    printf("%d",ans);
    return 0;
}