【BZOJ 1221】[HNOI2001] 软件开发

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1221

真·双倍经验

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000;
const int INF = 100000000;
 
int head[N],nxt[N],to[N],cost[N],flow[N],dis[N],inq[N];
int n,st,sc,ft,fc,arr[N],S,T,p,sur[N],FLOW[N]; 
queue<int> que;
  
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
#define id(x,ty) ((x)*2+ty)
inline void Add_Edge(int u, int v, int f, int c) {
    static int TT = 1;
    to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
    to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}
 
inline int SPFA() {
    memset(dis,127,sizeof(dis));
    memset(FLOW,0,sizeof(FLOW));
    que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
     
    while (!que.empty()) {
        int w = que.front(); que.pop(); inq[w] = 0;
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
            dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
            FLOW[to[i]] = min(FLOW[w], flow[i]);
            if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
        }
    } return FLOW[T];
}
 
inline int MCMF() {
    int ret = 0;
    for (int w=T,f;f=SPFA();w=T) 
        for (int t=sur[w];w!=S;t=sur[w]) 
            flow[t] -= f, 
            flow[t^1] += f,
            ret += cost[t]*f, 
            w = to[t^1];
    return ret;
}
 
int main(){
    n = read(); ft = read()+1; st = read()+1; p = read(); fc = read(); sc = read(); S = 0; T = 1;
    for (int i=1;i<=n;i++) arr[i] = read();
    for (int i=1;i<=n;i++) Add_Edge(S,id(i,0),arr[i],0), Add_Edge(id(i,1),T,arr[i],0);
    for (int i=1;i<n;i++) Add_Edge(id(i,0),id(i+1,0),INF,0);
    for (int i=1;i<=n;i++) if (i + ft <= n) Add_Edge(id(i,0),id(i+ft,1),INF,fc);
    for (int i=1;i<=n;i++) if (i + st <= n) Add_Edge(id(i,0),id(i+st,1),INF,sc);
    for (int i=1;i<=n;i++) Add_Edge(S,id(i,1),INF,p);
    printf("%d\n",MCMF());
    return 0;
}