网络流24题-洛谷p1251-餐巾计划问题

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const ll maxn=50050,maxm=500050,inf=2147483647;
struct {
    ll v,c,cost;
 node *next,*rev;
}*pree[maxn],*h[maxn],pool[maxm];
ll n,s,p,m,day,f,a[maxn],sum;
ll tot=0;
ll src,sink;
inline void addEdge(ll u,ll v,ll c,ll cost){
    node *p=&pool[++tot],*q=&pool[++tot];
    p->v=v;p->c=c;p->cost=cost;p->next=h[u];h[u]=p;p->rev=q;
  q->v=u;q->c=0;q->cost=-cost;q->next=h[v];h[v]=q;q->rev=p;
}
ll dis[maxn],q[maxn],pre_v[maxn];bool vis[maxn];

inline bool SPFA(){
   fill(dis+1,dis+n+1,inf);
    memset(vis,false,sizeof(vis));
  queue<ll> Q;
  vis[src]=1,dis[src]=0;
  Q.push(src);
    while(!Q.empty()){
      ll front=Q.front();
     Q.pop();
        vis[front]=false;
       for(node *p=h[front];p;p=p->next){
           if(p->c && dis[p->v]>dis[front]+p->cost){
               dis[p->v]=dis[front]+p->cost;
             pre_v[p->v]=front;
               pree[p->v]=p;
                if(!vis[p->v]){
                  vis[p->v]=1;
                 Q.push(p->v);
                }
           }
       }
   }
   return dis[sink]!=inf;
}*/
inline bool spfa(){
    for(ll i=1;i<maxn;i++) dis[i]=inf;
    for(ll i=1;i<maxn;i++) vis[i]=0;
    ll front=0,rear=0;
    vis[src]=1,dis[src]=0;
    q[rear++]=src;
    while(front<rear)
    {
        ll u=q[front++];
        vis[u]=0;
        for(node *p=h[u];p;p=p->next)
        {
            if(p->c>0 && dis[p->v]>dis[u]+p->cost)
            {
                dis[p->v]=dis[u]+p->cost;
                pre_v[p->v]=u;
                pree[p->v]=p;
                if(!vis[p->v])
                {
                    vis[p->v]=1;
                    q[rear++]=p->v;
                }
            }
        } 
    }
    if(dis[sink]<inf) return true;
    return false;
}

inline ll Update(){
 ll u=sink,ret=inf;
   while(u!=src){
      ret=min(ret,pree[u]->c);
      u=pre_v[u];
  }
    u=sink;
  while(u!=src){
      pree[u]->c-=ret;
      pree[u]->rev->c+=ret;
      u=pre_v[u];
  }
    return ret;
}
ll MaxFlow,Mincostflow;
inline void MinCostFlow(){
   ll ret=0;
    while(spfa()){
      ret=Update();
        MaxFlow+=ret;
        Mincostflow+=ret*dis[sink];
  }
}
inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}
inline void write(ll x) {
    ll y = 10, len = 1;
    while (y <= x) {
        y *= 10; len++;
    }
    while (len--) {
        y /= 10; putchar(x / y + 48);x %= y;
    }
}
int main(){
   day=read();
  for(ll i=1;i<=day;i++) a[i]=read();
  p=read();m=read();f=read();n=read();s=read();
    src=0,sink=2*day+1;
  for(ll i=1;i<=day;i++){
      addEdge(src,i,a[i],0);
       addEdge(day+i,sink,a[i],0);
  }
    for(ll i=1;i<=day;i++){
      if(i+1<=day) addEdge(i,i+1,inf,0);
       if(i+m<=day) addEdge(i,day+i+m,inf,f);
       if(i+n<=day) addEdge(i,day+i+n,inf,s);
       addEdge(src,day+i,inf,p); 
   }
    MinCostFlow();
   write(Mincostflow);
  return 0;
}