第二个点答案比了一下发现大了很多,两倍左右
by x义x @ 2019-07-15 15:32:00
拒绝QNDMX等言论,尤其是发了QNDMX之后代码都不看就跑的QAQ
by x义x @ 2019-07-15 15:34:10
(自己的答案是正确答案两倍左右)
by x义x @ 2019-07-15 15:39:02
你又刚学OI了。。。
~~f\*\*k.in, 我看过代码了~~
by encore @ 2019-07-15 15:39:40
这题炸int,还有你数组可能开小了
by wxwoo @ 2019-07-15 15:39:46
@[wxwoo](/space/show?uid=116659)
- 数组开的绝对够了(亲测再开大也还是一样)
- long long的问题我感觉该开的都已经开了呀QAQ
by x义x @ 2019-07-15 15:49:25
@[wxwoo](/space/show?uid=116659) int全改long long亲测完全没区别
by x义x @ 2019-07-15 15:51:59
这是目前的代码,和之前答案没有区别:
```cpp
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxN=10005,maxM=1000005,TT=10000;
const LL INF=0x3f3f3f3f3f3f3f3fLL;
LL V,E,S,T;
LL lnk[maxN];
LL pre[maxM],tgt[maxM],rev[maxM],cnt;LL val[maxM],wgt[maxM];
void add_E(LL u,LL v,LL f,LL c){
pre[++cnt]=lnk[u],tgt[cnt]=v,rev[cnt]=cnt+1,val[cnt]=f,wgt[cnt]=c,lnk[u]=cnt;
pre[++cnt]=lnk[v],tgt[cnt]=u,rev[cnt]=cnt-1,val[cnt]=0,wgt[cnt]=-c,lnk[v]=cnt;
}
LL q[maxN],h,t;
LL dis[maxN];bool inq[maxN];
LL fa_pos[maxN],fa_edge[maxN];
bool SPFA(){
memset(dis,63,sizeof(dis));
memset(inq,0,sizeof(inq));
h=t=0;q[++t]=S;dis[S]=0;inq[S]=1;
while(h!=t){
LL u=q[h=(h+1)%TT];inq[u]=0;
for(LL e=lnk[u];e;e=pre[e]) if(val[e])
if(dis[tgt[e]]>dis[u]+wgt[e]){
dis[tgt[e]]=dis[u]+wgt[e];
fa_pos[tgt[e]]=u;fa_edge[tgt[e]]=e;
if(!inq[tgt[e]]) q[t=(t+1)%TT]=tgt[e],inq[tgt[e]]=1;
}
}if(dis[T]!=INF) return 1;
else return 0;
}
LL min_cost,max_flow;
LL N;
LL r[2005];
LL p,m,f,n,s;
int main(){
// freopen("fuck.in","r",stdin);
cin>>N;
for(LL i=1;i<=N;i++) cin>>r[i];
cin>>p>>m>>f>>n>>s;
for(LL i=1;i<=N;i++){
add_E(1,2*i+1,INF,p); //买
add_E(2*i+1,2,r[i],0); //满流表示足够
add_E(1,2*i*2,r[i],0); //获得脏餐巾
if(i+1<=N) add_E(2*i+2,2*i+4,INF,0); //脏餐巾留到下一天
if(i+m<=N) add_E(2*i+2,2*(i+m)+1,INF,f);//快洗
if(i+n<=N) add_E(2*i+2,2*(i+n)+1,INF,s);//慢洗
}
V=2*N+2,S=1,T=2;
while(SPFA()){
LL d=INF;
for(LL x=T;x!=S;x=fa_pos[x]) d=min(d,val[fa_edge[x]]);
for(LL x=T;x!=S;x=fa_pos[x]){
val[fa_edge[x]]-=d;
val[rev[fa_edge[x]]]+=d;
}
max_flow+=d;min_cost+=d*dis[T];
}
printf("%lld",min_cost);
return 0;
}
```
by x义x @ 2019-07-15 17:53:23
``//获得脏餐巾``处把``2*i*2``改成``2*i+2``即可AC。此贴终结……
by x义x @ 2019-07-15 19:10:51