关键词:最小费用最大流
相关题目:$Luogu1251$

Solution

这道题求的是规定状态下的最小费用,可以想到用费用流

首先还是来讲如何建模(毕竟网络流也就是个建模。。)

首先考虑如何满足每天的餐巾数量这一最重要的限制条件,
可以想到从每一天向汇点连一条容量为$r[i]$(第 $i$ 天所需餐巾数量),费用为0

获取餐巾的方式有三种——
1. 以单价$a$买新的
2. 将旧餐巾以单价$c$送去快洗店,$b$天后才能用
3. 将旧餐巾以单价$e$送去快洗店,$d$天后才能用

我一开始是这么想的:
对于买新的,从源点向每天连一条容量$inf$费用为$a$的边
对于快洗店,从每天向$b$天后连一条容量$inf$费用$c$的边
对于快洗店,从每天向$d$天后连一条容量$inf$费用$e$的边
对于餐巾可以留着,从每天向第二天连一天容量$inf$费用0的边

这样显然是错的
这样建模没有分开旧餐巾和新餐巾,并不能保证送去洗的是否是用过的
新餐巾拿去洗岂不尬哉?

考虑拆点把一天拆成旧餐巾和新餐巾两部分,分别用$A$和$B$表示

每天要用$r[i]$个餐巾,分别从$B$向汇点、从源点向$A$连容量$r[i]$费用0的边,表示用$r[i]$条新餐巾,产生$r[i]$条旧餐巾

对于三种获取餐巾方式,
买新的:从源点向$B$连一条容量$inf$费用$a$的边
快洗店:从当天的$A$向$b$天后的$B$连一条容量$inf$费用$c$的边
慢洗店:同快洗店

然后由于餐巾可以放着不管,从每天的$A$向第二天的$A$连容量$INF$费用0的边

就完了。。(主要还是一个拆点比较难想?)

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <algorithm>
const int E=210000,N=4100;
using namespace std;
int n,r[N],a,b,c,d,e,s,t;
int head[N],to[E],w[E],f[E],nxt[E],cnt=1;
int last[N],pre[N],maxflow[N],vis[N],q[E],he,tail;
long long dis[N],ans;
inline void add(int u,int v,int val,int cost){
to[++cnt]=v,w[cnt]=val,f[cnt]=cost;
nxt[cnt]=head[u],head[u]=cnt;
}
inline void link(int u,int v,int val,int cost){
add(u,v,val,cost);
add(v,u,0,-cost);
}
inline void spfa(){
memset(dis,0x3f,sizeof dis); dis[s]=0;
memset(maxflow,0x3f,sizeof maxflow);
memset(vis,0,sizeof vis); vis[s]=1;
he=1,tail=0;
q[++tail]=s;
while(he<=tail){
int u=q[he]; he++;
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(w[i]>0&&dis[v]>dis[u]+f[i]){
pre[v]=u,last[v]=i;
dis[v]=dis[u]+f[i];
maxflow[v]=min(maxflow[u],w[i]);
if(!vis[v]) q[++tail]=v,vis[v]=1;
}
}
}
}
int main(int argc, char const *argv[]) {
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
s=2*n+1,t=2*n+2;
for(int i=1;i<=n;i++)
link(s,i,r[i],0),link(s,i+n,2e9,a),link(i+n,t,r[i],0);
//产生的旧餐巾 新买餐巾 向汇点连边保证每天餐巾数量恰好为r[i]
for(int i=1;i<n;i++)
link(i,i+1,2e9,0); //把旧餐巾留到第二天
for(int i=1;i<=n-b;i++)
link(i,i+b+n,2e9,c); //快洗店
for(int i=1;i<=n-d;i++)
link(i,i+d+n,2e9,e); //慢洗店
spfa();
while(dis[t]<1e9){
ans+=dis[t]*maxflow[t];
for(int u=t;u!=s;u=pre[u]){
w[last[u]]-=maxflow[t];
w[last[u]^1]+=maxflow[t];
}
spfa();
}
printf("%lld\n",ans);
return 0;
}