传送门 ↬\looparrowright

题目描述

一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 rir_i 块餐巾（$ i=1,2,\cdots,N$）。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分；或者把旧餐巾送到快洗部,洗一块需 mm 天,其费用为 ff 分;或者送到慢洗部,洗一块需 nn 天（n>mn>m），其费用为 ss 分（s<fs<f）。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

输入格式

由标准输入提供输入数据。文件第 11 行有 11 个正整数 NN，代表要安排餐巾使用计划的天数。
接下来的一行是餐厅在相继的 NN 天里,每天需用的餐巾数。
最后一行包含 55 个正整数 p,m,f,n,sp,m,f,n,s。pp 是每块新餐巾的费用；mm 是快洗部洗一块餐巾需用天数；ff 是快洗部洗一块餐巾需要的费用；nn 是慢洗部洗一块餐巾需用天数；ss 是慢洗部洗一块餐巾需要的费用。

输出格式

将餐厅在相继的 NN 天里使用餐巾的最小总花费输出。

输入输出样例

输入 #1

3
1 7 5
11 2 2 3 1

输出 #1

134

说明/提示

N⩽2000N\leqslant 2000，ri⩽10000000r_i\leqslant 10000000，p,f,s⩽10000p,f,s\leqslant10000。时限 4s4\mathrm s。

分析

题目中有说：每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部,以及多少块保存起来延期送洗；每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。也就是说，对于完整的一天，每天早晨至少要获得满足当天需求的赶紧餐巾，干净餐巾可以从快洗部或慢洗部获得，也可以直接买；每天晚上要决定脏餐巾的去处。每个状态有多种选择的问题，可以考虑分层图最短路，然而，对于此题，按照最短路的思想难以完成建图的工作；要使 NN 天内每一天都满足餐巾的使用需求，且要求费用最小，不妨进一步考虑最小费用最大流。
不妨就将 NN 天作为 NN 个节点，再考虑早晨和晚上的不同分工，就将每个点拆成代表【早晨，夜晚】的两个点。规定：代表早晨的点编号为 1∼N1\sim N，代表夜晚的点编号为 N+1∼2NN+1\sim 2N，源点 source\text{source} 的编号为 00，汇点 sink\text{sink} 的编号为 2N+12N+1。
编号为 1∼N1\sim N 节点的入边用于接受干净的餐巾，包括从慢洗部、快洗部洗好的餐巾，和之间买来的毛巾：其中一部分入边为源点向 1∼N1\sim N 节点的连边，容量为 +∞+\infty，单位费用为 pp，这些边用于供给干净的餐巾；另一部分为代表夜晚节点的出边，将脏餐巾送到快洗部属于夜晚的操作，会连向 mm 天后的早晨，费用为 ff，将脏餐巾送到慢洗部也是夜晚的操作，连向 nn 天后的早晨，费用为 ss。编号为 1∼N1\sim N 节点的出边都连向汇点，容量为 rir_i，费用为 00。
编号为 N+1∼2NN+1\sim 2N 的节点入边用于接受脏的餐巾：一部分入边的另一端为源点，这些边用于提供脏餐巾，容量为 rir_i（接受的仅仅是当天产生的脏餐巾），费用为 00；另一部分入边的另一端是前几天的夜晚，这些边提供前几天夜晚遗留下的脏餐巾，容量为 +∞+\infty，费用为 00。编号为 N+1∼2NN+1\sim 2N 的节点的出边用于处理脏毛巾：将脏餐巾送到快洗部属于夜晚的操作，会连向mm 天后的早晨，费用为 ff，将脏餐巾送到慢洗部也是夜晚的操作，连向 nn 天后的早晨，费用为 ss。编号为 1∼N1\sim N 节点的出边都连向汇点，容量为 rir_i，费用为 00。
按照上述方式建图，其最大流必为 ∑i=1Nri\sum\limits_{i=1}^N r_i，且汇点的每一条入边都满流，这就保证了每天的干净毛巾能够满足需求。网络的最小费用最大流即为答案。

代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P1251
Date: 7/29/2020
Description: Minimum-cost Flow
*******************************************************************/
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=2004<<2;
const int M=1000003;
struct E
{
	int to;
	ll cap;
	ll cost;
	int Next=-1;
}edge[M];
int head[N],tot;
bool inqueue[N];
ll incf[N],dis[N];
int pre[N];
int days;//餐巾使用计划天数
int source;//源点
int sink;//汇点
int p;//每块新餐巾费用
int m,f;//快洗 时间和费用
int n,s;//慢洗 时间和费用
ll r[N>>1];
void init();
inline void add_edge(int u,int v,ll cap,ll cost);
bool SPFA();
ll MCMF();
int main()
{
	cin>>days;
	int i;
	for(i=1;i<=days;i++) scanf("%lld",r+i);
	cin>>p>>m>>f>>n>>s;
	init();
	for(i=1;i<=days;i++)
	{
		add_edge(i,sink,r[i],0);//早晨的点连向汇点 满流时代表这天的毛巾够用
		add_edge(source,i+days,r[i],0);//晚上获得r[i]条脏毛巾
		add_edge(source,i,inf,p);//源点流向早上的点 可供给毛巾
		if(i+m<=days) add_edge(i+days,i+m,inf,f);//快洗
		if(i+n<=days) add_edge(i+days,i+n,inf,s);//慢洗
		if(i+1<=days) add_edge(i+days,i+1+days,inf,0);//脏毛巾存到下一天晚上
	}
	cout<<MCMF()<<endl;
	return 0;
}
void init()
{
	source=0;
	sink=2*days+1;
	tot=1;
	memset(head,-1,sizeof(head));
}
inline void add_edge(int u,int v,ll cap,ll cost)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].cost=cost;
	edge[tot].Next=head[u];
	head[u]=tot;
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].cost=-cost;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool SPFA()
{
	queue<int>q;
	memset(dis,inf,sizeof(dis));
	memset(inqueue,0,sizeof(inqueue));
	q.push(source);
	dis[source]=0;
	inqueue[source]=1;
	incf[source]=inf;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inqueue[x]=0;
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			if(!edge[i].cap) continue;//剩余容量为0，不在残量网络中。
			int y=edge[i].to;
			if(dis[y]>dis[x]+edge[i].cost)
			{
				dis[y]=dis[x]+edge[i].cost;//松弛操作
				incf[y]=min(incf[x],edge[i].cap);//最小剩余容量
				pre[y]=i;//记录前驱
				if(!inqueue[y])
				{
					inqueue[y]=1;
					q.push(y);
				}
			}
		}
	}
	if(dis[sink]==inf) return 0;//汇点不可达，已经求出最大流
	else return 1;
}
ll MCMF()
{
	ll maxflow,mincost;
	maxflow=mincost=0;
	while(SPFA())
	{
		int x=sink;
		//沿着前驱倒着走增广路
		while(x!=source)
		{
			int y=pre[x];
			edge[y].cap-=incf[sink];
			edge[y^1].cap+=incf[sink];
			x=edge[y^1].to;
		}
		maxflow+=incf[sink];
		mincost+=dis[sink]*incf[sink];
	}
	return mincost;
}