题目链接
题解
考虑上下界网络流
对于没个时间点拆成两个点(A,A')
由S点连向(A)限制最小流入量，处理这部分流量时相当于计算花费
然后就是考虑如和相依状态转移,建边
不要忘了剩下干净的
代码
// luogu-judger-enable-o2
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::queue;
using std::min;
#define INF 0x7fffffff
const int maxn = 770000;
inline int read() {
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
return x;
}
int N,S,T,ned[maxn],p,m,f,n,s;
struct node{
int u,v,flow,next,cost;
}edge[maxn];int head[maxn],num=1;
inline void add_edge(int u,int v,int flow,int cost) {
edge[++num].v=v;edge[num].u=u,edge[num].flow=flow,edge[num].next=head[u];head[u]=num;
edge[num].cost=cost;
edge[++num].v=u;edge[num].u=v,edge[num].flow=0;edge[num].next=head[v];head[v]=num;
edge[num].cost=-cost;
}
int Min_cost=0;
int pre[maxn],dis[maxn];
bool vis[maxn];
bool spfa() {
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
queue<int>que;
que.push(S),vis[S]=1;dis[S]=0;
while(!que.empty()) {
int u=que.front();que.pop();
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(edge[i].flow && dis[v]>dis[u]+edge[i].cost) {
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if(!vis[v]) que.push(v),vis[v]=1;
}
}
vis[u]=0;
}
if(dis[T]!=0x3f3f3f3f)return true;
else return false;
}
int calc() {
int ret=0,maxx=0x3f3f3f3f;
for(int i=T;i!=S;i=edge[pre[i]].u)
maxx=min(edge[pre[i]].flow,maxx);
for(int i=T;i!=S;i=edge[pre[i]].u) {
edge[pre[i]].flow-=maxx;
edge[pre[i]^1].flow+=maxx;
ret+=maxx*edge[pre[i]].cost;
}
return ret;
}
long long ans=0;
void mcmf() {
while(spfa())
ans+=calc();
}
int main() {
N=read();
for(int i=1;i<=N;++i) ned[i]=read();
p=read(),m=read(),f=read(),n=read(),s=read();
T=N*2+1;
for(int i=1;i<=N;++i) {
add_edge(S,i,ned[i],0);
add_edge(N+i,T,ned[i],0);
}
for(int i=1;i<=N;++i) {
if(i+1<=N)add_edge(i,i+1,INF,0);
if(i+m<=N)add_edge(i,N+i+m,INF,f);
if(i+n<=N)add_edge(i,N+i+n,INF,s);
add_edge(S,i+N,INF,p);
}
mcmf();
printf("%lld
",ans);
return 0;
}