LuoguP2223 [HNOI2001]软件开发 题解

(Updated: )
oi

Description

某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

$1\leq f,fA,fB\leq 60,1\leq n\leq 1000$

Solution

首先，拆点，把每个点拆成入点和出点，分别为 $i$ 和 $i+n$。

考虑每天有且只有 $n_i$ 个毛巾，故建立超级源点 $S$ 和超级汇点 $T$，并在 $S$ 和 $i$ 之间、$i+n$ 和 $T$ 之间连接容量 $inf$，费用 $0$ 的边。

接下来考虑各个方法。

对于 $a$ 和 $b$ 只要在 $i$ 天和 $i+a$ 天之间连一条容量为 $inf$，费用为 $fa$ 的边，$b$ 同理。

每天的新毛巾可以留到明天，所以 $i$ 和 $i+1$ 之间连接一条容量为 $inf$，费用为 $0$ 的边。

最后每天可以进货，所以 $S$ 和 $i+n$ 连 $inf,f$。

最后跑一遍费用流。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1010;
int n,a,b,f,fa,fb,c[N],cnt,S,T,in[N],out[N],inf=2e9,fir[N<<1],son[N<<4],nxt[N<<4],w[N<<4],cost[N<<4],tot=1,dis[N<<1],vis[N<<1],Cost;
I void add(CI x,CI y,CI z,CI c){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c;}
#define Add(x,y,z,c) (add(x,y,z,c),add(y,x,0,-c))
queue<int> q;
#define to son[i]
struct Edge{int son,id;}pre[N<<1];
I bool bfs(){
W(!q.empty()) q.pop();memset(dis,63,sizeof(dis));inf=dis[0];dis[S]=0;memset(vis,0,sizeof(vis));q.push(S);W(!q.empty()){
RI u=q.front(),i;q.pop();for(i=fir[u];i;i=nxt[i]) if(w[i]>0&&dis[to]>dis[u]+cost[i]) dis[to]=dis[u]+cost[i],
pre[to]=(Edge){u,i},!vis[to]&&(q.push(to),vis[to]=1);vis[u]=0;
}return dis[T]<inf;
}
I void EK(){
Cost=0;W(bfs()){
RI i,Min=inf;for(i=T;i^S;i=pre[i].son) Min=min(Min,w[pre[i].id]);
for(i=T;i^S;i=pre[i].son) w[pre[i].id]-=Min,w[pre[i].id^1]+=Min;
Cost+=Min*dis[T];
}return ;
}
int main(){
RI i;for(S=++cnt,T=++cnt,read(n,a,b,f,fa,fb),i=1;i<=n;i++) read(c[i]),in[i]=++cnt,out[i]=++cnt,Add(S,in[i],c[i],0),Add(out[i],T,c[i],0),Add(S,out[i],inf,f);
for(a++,b++,i=1;i<=n;i++) i+a<=n&&(Add(in[i],out[i+a],inf,fa),0),i+b<=n&&(Add(in[i],out[i+b],inf,fb),0),i<n&&(Add(in[i],in[i+1],inf,0),0);
return EK(),writeln(Cost),0;
}