只有40,哪位大佬能帮忙看看? (注:除了建图应该都没问题,各位重点关注建图即可)
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
//#undef int
using std::queue;
int n;
int m,t1,m1,t2,m2;
//int s,t;
int st,en;
int x,y,z,w;
int h[50005],to[50005],next[50005],f[50005],c[50005];
int cnt=1;
void add(int x,int y,int z,int cost){
to[++cnt]=y;
next[cnt]=h[x];
f[cnt]=z;
c[cnt]=cost;
h[x]=cnt;
}
void ad(int x,int y,int z,int cost){
add(x,y,z,cost);
add(y,x,-z,0);
}
int dis[50005],flow[50005],pre[50005],last[50005];
bool vis[50005];
bool spfa(){
memset(dis,0x7f*1000,sizeof dis);
memset(flow,0x7f*1000,sizeof flow);
memset(vis,false,sizeof vis);
queue<int>q;
q.push(st);
dis[st]=0;
vis[st]=true;
pre[en]=-1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=false;
for(int i=h[x];i;i=next[i]){
int v=to[i];
if(f[i]>0&&dis[v]>dis[x]+c[i]){
dis[v]=dis[x]+c[i];
pre[v]=x;
last[v]=i;
flow[v]=std::min(flow[x],f[i]);
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
return ~pre[en];
}
int fl,co;
void mcmf(){
while(spfa()){
int u=en;
fl+=flow[en];
co+=flow[en]*dis[en];
while(u!=st){
f[last[u]]-=flow[en];
f[last[u]^1]+=flow[en];
u=pre[u];
}
}
}
signed main(){
// freopen("st.txt","r",stdin);
scanf("%lld",&n);
st=0;
en=2*n+1;
for(int i=1;i<=n;i++){
scanf("%lld",&x);
ad(st,i,x,0);
ad(i+n,en,x,0);
}
scanf("%lld%lld%lld%lld%lld",&m,&t1,&m1,&t2,&m2);
for(int i=1;i<=n;i++){
if(i+1<=n)ad(i,i+1,0x7f*1000,0);
if(i+t1<=n)ad(i,i+n+t1,0x7f*1000,m1);
if(i+t2<=n)ad(i,i+n+t2,0x7f*1000,m2);
ad(st,i+n,0x7f*1000,m);
}
mcmf();
printf("%lld",co);
return 0;
}