应该比较好看出来是费用流,那么就考虑怎么构图
首先我们把一天拆成两个点,XI,YI,分别代表这一天买了多少
和洗多少,再加入源和汇S,T
1.每一天我们可以买新的毛巾,所以连接一条从S到XI的边,流量为正无穷(因为可以买好多),费用为f
2.然后我们对于买来的毛巾可以洗,每天都产生need[i]的毛巾可以洗,那么连一条从S到YI的边,
流量为need[i],费用为0(因为只决定要洗,没有确定洗的方案,所以先不算费用)
3.每一条要用a方法洗的毛巾,我们连一条从YI到X(I+a+1)的边,流量为正无穷(下文解释),费用为fa的
4.每一条要用b方法洗的毛巾,我们连一条从YI到X(I+b+1)的边,流量为正无穷(下文解释),费用为fb的
5.因为每天剩下的毛巾,我们可以不当天洗,所以连接一条从YI到Y(I+1)的边,流量为正无穷,费用为0(所以每天可以洗
的毛巾的个数是可能会很多的,4,5建的边流量要是正无穷)
6.那么我们每天买的毛巾除了洗,还可以不洗,也就是直接扔掉,所以连一条XI到T的边,流量为need[i],费用为0
/************************************************************** Problem: 1221 User: BLADEVIL Language: Pascal Result: Accepted Time:1952 ms Memory:8120 kb****************************************************************/ //By BLADEVILvar n, a, b, f, fa, fb :longint; need :array[0..1010] of longint; pre, other,len :array[0..500010] of longint; cost :array[0..500010] of longint; last :array[0..4010] of longint; ss, tt :longint; que :array[0..5000] of longint; dis :array[0..5000] of longint; flag :array[0..5000] of boolean; father :array[0..5000] of longint; ans :int64; l :longint; function min(a,b:longint):longint;begin if a>b then min:=b else min:=a;end; procedure connect(a,b,c,d:longint);begin inc(l); pre[l]:=last[a]; last[a]:=l; other[l]:=b; len[l]:=c; cost[l]:=d;end; procedure init;var i :longint; use :longint;begin read(n,a,b,f,fa,fb); for i:=1 to n do read(need[i]); l:=1; ss:=2*n+1; tt:=2*n+2; for i:=1 to n do begin connect(ss,2*i-1,maxlongint,f); connect(2*i-1,ss,0,-f); connect(2*i-1,tt,need[i],0); connect(tt,2*i-1,0,0); connect(ss,2*i,need[i],0); connect(2*i,ss,0,0); use:=i+a+1; if use<=n then begin use:=use*2-1; connect(2*i,use,maxlongint,fa); connect(use,2*i,0,-fa); end; use:=i+b+1; if use<=n then begin use:=use*2-1; connect(2*i,use,maxlongint,fb); connect(use,2*i,0,-fb); end; end; for i:=1 to n-1 do begin connect(2*i,2*i+2,maxlongint,0); connect(2*i+2,2*i,0,0); end;end; function spfa:boolean;var q, p, cur :longint; h, t :longint;begin filldword(dis,sizeof(dis) div 4,maxlongint div 10); que[1]:=ss; dis[ss]:=0; h:=0; t:=1; while t<>h do begin h:=h mod 5000+1; cur:=que[h]; flag[cur]:=false; q:=last[cur]; while q<>0 do begin p:=other[q]; if len[q]>0 then begin if dis[p]>dis[cur]+cost[q] then begin father[p]:=q; dis[p]:=dis[cur]+cost[q]; if not flag[p] then begin t:=t mod 5000+1; que[t]:=p; flag[p]:=true; end; end; end; q:=pre[q]; end; end; if dis[tt]=maxlongint div 10 then exit(false) else exit(true);end; procedure update;var cur :longint; low :longint; begin low:=maxlongint div 10; cur:=tt; while cur<>ss do begin low:=min(low,len[father[cur]]); cur:=other[father[cur] xor 1]; end; cur:=tt; while cur<>ss do begin dec(len[father[cur]],low); inc(len[father[cur] xor 1],low); inc(ans,low*cost[father[cur]]); cur:=other[father[cur] xor 1]; end;end; procedure main;begin while spfa do update; writeln(ans);end; begin init; main;end.