首页 > 其他 > 详细

「考试总结2020-08-06」遗憾

时间:2020-08-06 20:42:48      阅读:124      评论:0      收藏:0      [点我收藏+]

include<bits/stdc++.h>

using namespace std;

define int long long

namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
while(isdigit(k)) res=res10+k-‘0‘,k=getchar();
return res
f;
}
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=4010,M=100010;
struct node{
int to,nxt,lim,cost;
}e[M<<1];
int head[N],cnt=1,ans,incf[N],n,pre[N],d[N],c[N],s,t,c1,c2,m2,m1,p,mx;
queue q; bool vis[N];
inline void adde(int u,int v,int w,int c)
{
e[++cnt].to=v; e[cnt].nxt=head[u]; e[cnt].lim=w; e[cnt].cost=c;
return head[u]=cnt,void();
}
inline void add(int u,int v,int w,int c){return adde(u,v,w,c),adde(v,u,0,-c);}
inline bool spfa()
{
while(q.size()) q.pop(); memset(d,0x3f,sizeof(d));
q.push(s); d[s]=0; vis[s]=1; incf[s]=inf;
while(!q.empty())
{
int fr=q.front(); q.pop(); vis[fr]=0;
for(int i=head[fr];i;i=e[i].nxt)
{
if(!e[i].lim) continue;
int nt=e[i].to;
if(d[nt]>d[fr]+e[i].cost)
{
d[nt]=d[fr]+e[i].cost; pre[nt]=i; incf[nt]=min(incf[fr],e[i].lim);
if(!vis[nt]) vis[nt]=1,q.push(nt);
}
}
}
return d[t]!=inf;
}
inline void update()
{
int x=t;
while(x!=s)
{
e[pre[x]].lim-=incf[t];
e[pre[x]^1].lim+=incf[t];
x=e[pre[x]^1].to;
}
return mx+=incf[t],ans+=incf[t]*d[t],void();
}
signed main()
{
n=read(); m1=read(); m2=read(); p=read(); c1=read(); c2=read();
for(int i=1;i<=n;++i) c[i]=read();
s=n<<1|1; t=s+1;
for(int i=1;i<=n;++i)
{
if(i+m1+1<=n) add(i+n,i+m1+1,inf,c1);
if(i+m2+1<=n) add(i+n,i+m2+1,inf,c2);
if(i+1<=n) add(i+n,i+1+n,inf,0);
add(s,i,inf,p);
add(s,i+n,c[i],0);
add(i,t,c[i],0);
}
while(spfa()) update();
printf("%lld\n",ans);
return 0;
}
}
signed main(){return yspm::main();}

「考试总结2020-08-06」遗憾

原文:https://www.cnblogs.com/yspm/p/13448508.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!