rt,心态已经炸了,下载了第一个数据点,是没有问题的,本地和IDE上都正确。希望大佬能帮忙指出错误qwq。ps:第一个数据点是样例
#include<bits/stdc++.h>
#define dg(a) ((a)<'0'||(a)>'9')
#define Maxn 20000000009
#define int long long
#define Max 5009
using namespace std;
bool vis[Max];
int len=-1,lst[Max]; // 建边先 ++len ,所以相当于下标从零开始
int h[Max],flow,st,ed;
int pw,f1,f2,d1,d2,n,a[Max];
struct node{int id,x;};
bool operator <(node _a,node _b){_a.x<_b.x;}
struct edge{int x,y,c,w,nxt;}p[Max<<4];
void read(int &r)
{
r=0;char ch='t',f;ch=getchar();
while(dg(ch)){f=ch;ch=getchar();}
while(!dg(ch)){r=(r<<3)+(r<<1)+ch-'0';ch=getchar();}
if(f=='-')r=-r;
}
void ins(int x,int y,int c,int w)
{
len++;
p[len].x=x;p[len].y=y;
p[len].c=c;p[len].w=w;
p[len].nxt=lst[x];lst[x]=len;
}
bool bfs()
{
int u=Maxn*100000;
for(int i=0;i<=ed;i++)h[i]=u;
h[st]=0;
node t;t.id=st,t.x=0;
priority_queue<node>q;q.push(t);
while(!q.empty())
{
int x=q.top().id;q.pop();vis[x]=0;
for(int k=lst[x];k!=-1;k=p[k].nxt)
{
int y=p[k].y;
if(h[y]>h[x]+p[k].w&&p[k].c>(int)0)
{
h[y]=h[x]+p[k].w;
if(!vis[y])
{
vis[y]=1;
t.id=y;t.x=h[y];
q.push(t);
}
}
}
}
return h[ed]!=h[0];
}
int dinic(int x,int w)
{
if(x==ed)return w;
int s=0;vis[x]=1;
for(int k=lst[x];k!=-1;k=p[k].nxt)
{
int y=p[k].y;
if(h[y]==h[x]+p[k].w&&p[k].c>(int)0&&s<w&&!vis[y])
{
int t=dinic(y,min(w-s,p[k].c));
s+=t;
flow+=t*p[k].w;
p[k].c-=t;p[k^1].c+=t;
}
}
vis[x]=0;
if(s==0)h[x]=0;
return s;
}
signed main()
{
read(n);
st=2*n+1;ed=st+1;
memset(lst,-1,sizeof(lst));
for(int i=1;i<=n;i++)
{
int x;read(x);a[i]=x;
ins(st,i+n,x,0);ins(i+n,st,0,0);//还回统计过的衣服
ins(i,ed,x,0);ins(ed,i,0,0);//去统计衣服
}
read(pw);
read(d1);read(f1);read(d2);read(f2);
for(int i=1;i<=n-d1;i++)
{
ins(i+n,i+d1,Maxn,f1);//快洗
ins(i+d1,i+n,0,-f1);
}
for(int i=1;i<=n-d2;i++)
{
ins(i+n,i+d2,Maxn,f2);//慢洗
ins(i+d2,i+n,0,-f2);
}
for(int i=1;i<n;i++)
{
ins(st,i,a[i],pw);ins(i,st,0,-pw);//买餐巾
ins(i+n,i+n+1,Maxn,0);//留盘子
ins(i+n+1,i+n,0,0);
}
ins(st,n,a[n],pw);ins(n,st,0,-pw);
int ans=0;
while(bfs())ans+=dinic(st,Maxn*1000);
printf("%lld",flow);
return 0;
}