[cogs461] [网络流24题#10] 餐巾 [网络流，最小费用最大流]

建图：从源点向第一层连边，第一层表示当天用掉多少餐巾，第二层表示当天需要多少餐巾，所以注意购买餐巾的边容量为无穷大，要从源点开始连向第二层的点，每天可能有剩余，在第一层内表示为流入第二天的节点。具体见代码，第一次写费用流，不知道模板对不对。。。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <ctime>

#include <cstdlib>

#include <queue>

using namespace std;

template<const int _n,const int _m>

struct Edge

{

    struct Edge_base { int    to,next,w,c; }e[_m];

    int    cnt,p[_n];

    Edge() { clear(); }

    int    start(const int x) { return p[x]; }

    void    insert(const int x,const int y,const int z,const int zz)

    { e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; e[cnt].c=zz; p[x]=cnt; return ; }

    void    clear() { cnt=,memset(p,,sizeof(p)); }

    Edge_base&    operator[](const int x) { return e[x]; }

};

int    n,Dis[],SSS,TTT,cur[],a[];

int    Cost,Flow;

bool    visited[];

Edge<,>    e;

bool    Spfa(const int S)

{

    int    i,t,temp;

    queue<int>    Q;

    memset(Dis,0x3f,sizeof(Dis));

    Dis[S]=;

    visited[S]=true;

    Q.push(S);

    while(!Q.empty())

    {

        t=Q.front(),Q.pop();visited[t]=false;

        for(i=e.start(t);i;i=e[i].next)

        {

            temp=e[i].to;

            if(e[i].w && Dis[t]+e[i].c<Dis[temp])

            {

                Dis[temp]=Dis[t]+e[i].c;

                if(!visited[temp])

                {

                    visited[temp]=true;

                    Q.push(temp);

                }

            }

        }

    }

    return Dis[TTT]!=0x3f3f3f3f;

}

int    Dfs(const int S,const int bk)

{

    if(S==TTT)return bk;

    visited[S]=true;

    int    rest=bk;

    for(int &i=cur[S];i;i=e[i].next)

    {

        if(!visited[e[i].to] && Dis[S]+e[i].c==Dis[e[i].to] && e[i].w)

        {

            int    flow=Dfs(e[i].to,min(rest,e[i].w));

            Cost+=flow*e[i].c;

            e[i].w-=flow;

            e[i^].w+=flow;

            if((rest-=flow)<=)break;

        }

    }

    if(bk==rest)Dis[S]=0x3f3f3f3f;

    visited[S]=false;

    return bk-rest;

}

pair<int,int>    Dinic()

{

    while(Spfa(SSS))

    {

        memcpy(cur,e.p,sizeof(cur));

        Flow+=Dfs(SSS,0x3f3f3f3f);

    }

    return make_pair(Flow,Cost);

}

int main()

{

    freopen("napkin.in","r",stdin);

    freopen("napkin.out","w",stdout);

    int    i,newn,ts,cs,tf,cf;

    scanf("%d",&n);

    for(i=;i<=n;++i)scanf("%d",&a[i]);

    scanf("%d%d%d%d%d",&newn,&ts,&cs,&tf,&cf);

    SSS=n+n+;TTT=SSS+;

    for(i=;i<=n;++i)

    {

        e.insert(SSS,i,a[i],),e.insert(i,SSS,,);

        e.insert(i+n,TTT,a[i],),e.insert(TTT,i+n,,);

        e.insert(SSS,i+n,0x3f3f3f3f,newn),e.insert(i+n,SSS,,-newn);

        if(i!=n)e.insert(i,i+,0x3f3f3f3f,),e.insert(i+,i,,);

        if(i+tf<=n)e.insert(i,i+tf+n,0x3f3f3f3f,cf),e.insert(i+tf+n,i,,-cf);

        if(i+ts<=n)e.insert(i,i+ts+n,0x3f3f3f3f,cs),e.insert(i+ts+n,i,,-cs);

    }

    printf("%d\n",Dinic().second);

    return ;

}