洛谷P1251 餐巾计划问题——费用流
题目介绍题目描述输入格式输出格式输入输出样例
题解代码
题目介绍
链接: 传送门.
题目描述
一个餐厅在相继的 N 天里,每天需用的餐巾数不尽相同。假设第 i天需要 ri块餐巾( i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 p 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 n天(n>m),其费用为 s 分(s<f)。 每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。 试设计一个算法为餐厅合理地安排好 N天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入格式
由标准输入提供输入数据。文件第 1 行有 1 个正整数 N，代表要安排餐巾使用计划的天数。 接下来的一行是餐厅在相继的 N天里,每天需用的餐巾数。 最后一行包含5个正整数p,m,f,n,s。p 是每块新餐巾的费用; m 是快洗部洗一块餐巾需用天数; f是快洗部洗一块餐巾需要的费用; n是慢洗部洗一块餐巾需用天数; s 是慢洗部洗一块餐巾需要的费用。
输出格式
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
输入输出样例
输入 #1 3 1 7 5 11 2 2 3 1
输出 #1 134
说明/提示 N<=2000 ri<=10000000 p,f,s<=10000 时限4s
题解
可以看出是费用流的题目。关键在于建网络 首先关注网络的性质： (1)限制每一天使用餐巾数量：需要从源点连边，或者向汇点连容量为限制数量的边。 (2)每一天开始使用干净的毛巾，可以多种来源(来源数量不易约束)，故以出边限制每日使用数量；结束时需处理脏毛巾，出边种类多，以入边容量限制。 (3)脏毛巾可以慢洗后+m天使用，或快洗+n天后使用，或留到下一天仍为脏毛巾 (4)干净毛巾除了(3)洗获得，也可以直接购买
建立网络如下： (1)每一天结点分为开始和结束结点；开始结点向超级汇点T连边，容量为r[i],cost=0；超级源点向结束结点连边,容量r[i],cost=0 (2)对每一天结束结点 a.慢洗，向+m天后开始结点连边，容量INF,cost=f; b.快洗，向+n天后开始结点连边，容量INF,cost=s c.延迟洗，向+1天后的结束结点连边，容量为INF，cost=0 (3)对每一开始结点，还可以直接购买，由源点S向其连边，容量INF，cost=p;
建立网络后最小费用最大流即可。
代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std
;
typedef long long ll
;
const int maxn
=2005;
const ll INF
=0x3f3f3f3f3f3f3f3f;
const int inf
=0x3f;
class Edge{
public:
ll to
,cap
,cost
,nxt
,rev
;
};
int head
[maxn
<<1];
Edge edge
[maxn
<<5];
int cnt
=1;
int N
,r
,S
,T
;
void add(ll u
,ll v
, ll cap
, ll cost
){
edge
[cnt
].to
=v
;edge
[cnt
].cap
=cap
;edge
[cnt
].cost
=cost
;edge
[cnt
].nxt
=head
[u
];edge
[cnt
].rev
=cnt
+1; head
[u
]=cnt
++;
edge
[cnt
].to
=u
;edge
[cnt
].cap
=0; edge
[cnt
].cost
=-cost
;edge
[cnt
].nxt
=head
[v
];edge
[cnt
].rev
=cnt
-1; head
[v
]=cnt
++;
}
bool vis
[maxn
<<1];
int pre
[maxn
<<1],preEdge
[maxn
<<1];
ll dis
[maxn
<<1];
ll flow
[maxn
<<1];
ll h
[maxn
<<1];
bool Dkjistra(int S
, int T
){
memset(vis
,false,sizeof(vis
));
memset(dis
, inf
, sizeof(dis
));
memset(flow
, inf
, sizeof(flow
));
priority_queue
<pair
<int, int> > que
;
dis
[S
] = 0;
que
.push(make_pair(-dis
[S
], S
) );
while(!que
.empty() ){
int u
= que
.top().second
; que
.pop();
if(vis
[u
]) continue;
vis
[u
] = true;
for(int i
=head
[u
]; i
; i
=edge
[i
].nxt
){
Edge
&e
= edge
[i
];
if(vis
[e
.to
]) continue;
if(e
.cap
>0 && dis
[e
.to
] > dis
[u
] + e
.cost
+ h
[u
] - h
[e
.to
]){
dis
[e
.to
] = dis
[u
] + e
.cost
+ h
[u
] - h
[e
.to
];
pre
[e
.to
] = u
;
preEdge
[e
.to
] = i
;
flow
[e
.to
] = min(flow
[u
], e
.cap
);
que
.push(make_pair(-dis
[e
.to
], e
.to
));
}
}
}
for(int i
=1;i
<=T
;i
++) h
[i
] += dis
[i
];
return dis
[T
] != INF
;
}
void MCMF(){
ll maxflow
= 0;
ll mincost
= 0;
while(Dkjistra(S
, T
)){
maxflow
+= flow
[T
];
mincost
+= flow
[T
] * h
[T
];
int now
= T
;
while(now
!=S
){
Edge
&e
= edge
[preEdge
[now
]];
e
.cap
-= flow
[T
];
edge
[e
.rev
].cap
+= flow
[T
];
now
= pre
[now
];
}
}
printf("%lld\n", mincost
);
}
int main(){
scanf("%d",&N
);
S
=2*N
+1,T
=2*N
+2;
for(int i
=1;i
<=N
;i
++){
scanf("%d",&r
);
add(S
,i
+N
,r
,0);
add(i
,T
,r
,0);
}
int p
,m
,f
,n
,s
;
scanf("%d%d%d%d%d",&p
,&m
,&f
,&n
,&s
);
for(int i
=1;i
<=N
;i
++){
add(S
,i
,INF
,p
);
if(i
+m
<=N
) add(i
+N
,i
+m
,INF
,f
);
if(i
+n
<=N
) add(i
+N
,i
+n
,INF
,s
);
if(i
+1<=N
) add(i
+N
,i
+N
+1,INF
,0);
}
MCMF();
}
