AC日记——餐巾计划问题 洛谷 P1084

餐巾计划问题

思路：

　　氧气优化水过；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 4005

#define maxque 1000005

#define INF 0x7fffffff

#define ll long long

ll n,head[maxn],E[maxque],V[maxque],W[maxque],F[maxque];

ll pi,qt,qc,st,sc,s,t,cnt=,day[maxn],pre[maxn],dis[maxn];

ll que[maxque],ans;

bool if_[maxn];

inline void in(ll &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void edge_add(ll u,ll v,ll w,ll f)

{

    E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,F[cnt]=f,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,W[cnt]=-w,F[cnt]=,head[v]=cnt;

}

bool spfa()

{

    for(ll i=s;i<=t;i++)dis[i]=INF,if_[i]=false,pre[i]=-;

    ll h=maxque>>,tail=h+,now;que[h]=s,if_[s]=true,dis[s]=;

    while(h<tail)

    {

        now=que[h++],if_[now]=false;

        for(ll i=head[now];i;i=E[i])

        {

            if(F[i]>&&W[i]+dis[now]<dis[V[i]])

            {

                pre[V[i]]=i,dis[V[i]]=dis[now]+W[i];

                if(!if_[V[i]])

                {

                    if(dis[V[i]]<=dis[que[h]]&&h<tail) que[--h]=V[i];

                    else que[tail++]=V[i];

                    if_[V[i]]=true;

                }

            }

        }

    }

    return dis[t]!=INF;

}

int main()

{

    in(n),s=,t=n*+;ll pos,now;

    for(ll i=;i<=n;i++)in(day[i]);

    in(pi),in(qt),in(qc),in(st),in(sc);

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

    {

        edge_add(s,i,pi,INF);

        edge_add(i,t,,day[i]);

        edge_add(s,i+n,,day[i]);

        if(i+qt<=n) edge_add(i+n,i+qt,qc,INF);

        if(i+st<=n) edge_add(i+n,i+st,sc,INF);

        if(i!=n) edge_add(i+n,i+n+,,INF);

    }

    while(spfa())

    {

        now=t,pos=INF;

        while(pre[now]!=-)

        {

            pos=min(pos,F[pre[now]]);

            now=V[pre[now]^];

        }

        now=t,ans+=dis[t]*pos;

        while(pre[now]!=-)

        {

            F[pre[now]]-=pos;

            F[pre[now]^]+=pos;

            now=V[pre[now]^];

        }

    }

    printf("%lld\n",ans);

    return ;

}