40分,大样例WA了,没有输出。
应输出 83144953114,我没输出........
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
const int inf=1<<30;
using namespace std;
int n,ct,s=0,t=300005,p,m1,f,n1,ss,ans;
int head[500005],ver[500005],Next[500005],edg[500005],cost[500005],tot=1;
void add(int x,int y,int z,int c){
ver[++tot]=y,Next[tot]=head[x],head[x]=tot,edg[tot]=z,cost[tot]=c;
ver[++tot]=x,Next[tot]=head[y],head[y]=tot,edg[tot]=0,cost[tot]=-c;
}
int pre[500005],dis[500005],incf[500005],inq[500005];
int spfa(){
for(int i=0;i<=500005;i++) dis[i]=inf,inq[i]=0;
queue<int>q;
q.push(s);
inq[s]=1;
dis[s]=0;
incf[s]=inf;
while(q.size()){
int x=q.front();
q.pop();
inq[x]=0;
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!edg[i]) continue;
if(dis[y]>dis[x]+cost[i]){
dis[y]=dis[x]+cost[i];
incf[y]=min(incf[x],edg[i]);
pre[y]=i;
if(!inq[y]){
inq[y]=1;
q.push(y);
}
}
}
}
return dis[t]!=inf;
}
void Update(){
int x=t;
while(x!=s){
int i=pre[x];
edg[i]-=incf[t];
edg[i^1]+=incf[i];
x=ver[i^1];
}
ans+=dis[t]*incf[t];
}
signed main(){
freopen("EK.in","r",stdin);
freopen("EK.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>ct;
add(s,i,ct,0); add(i+n,t,ct,0);
}
cin>>p>>m1>>f>>n1>>ss;
for(int i=1;i<=n;i++){
if(i+1<=n)
add(i,i+1,inf,0);
if(i+m1<=n)
add(i,i+n+m1,inf,f);
if(i<=n1)
add(i,i+n+n1,inf,ss);
add(s,i+n,inf,p);
}
while(spfa()){
Update();
}
cout<<ans;
return 0;
}
赏一关注,谢谢大佬! qwq