传送门 ↬ \looparrowright ↬
题目描述
一个餐厅在相继的 N N N 天里,每天需用的餐巾数不尽相同。假设第 i i i 天需要 r i r_i r i 块餐巾($ i=1,2,\cdots,N$)。餐厅可以购买新的餐巾,每块餐巾的费用为 p p p 分;或者把旧餐巾送到快洗部,洗一块需 m m m 天,其费用为 f f f 分;或者送到慢洗部,洗一块需 n n n 天(n > m n>m n > m ),其费用为 s s s 分(s < f s<f s < f )。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 N N N 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入格式
由标准输入提供输入数据。文件第 1 1 1 行有 1 1 1 个正整数 N N N ,代表要安排餐巾使用计划的天数。
接下来的一行是餐厅在相继的 N N N 天里,每天需用的餐巾数。
最后一行包含 5 5 5 个正整数 p , m , f , n , s p,m,f,n,s p , m , f , n , s 。p p p 是每块新餐巾的费用;m m m 是快洗部洗一块餐巾需用天数;f f f 是快洗部洗一块餐巾需要的费用;n n n 是慢洗部洗一块餐巾需用天数;s s s 是慢洗部洗一块餐巾需要的费用。
输出格式
将餐厅在相继的 N N N 天里使用餐巾的最小总花费输出。
输入输出样例
输入 #1
3
1 7 5
11 2 2 3 1
输出 #1
134
说明/提示
N ⩽ 2000 N\leqslant 2000 N ⩽ 2000 ,r i ⩽ 10000000 r_i\leqslant 10000000 r i ⩽ 10000000 ,p , f , s ⩽ 10000 p,f,s\leqslant10000 p , f , s ⩽ 10000 。时限 4 s 4\mathrm s 4 s 。
分析
题目中有说:每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗;每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。也就是说,对于完整的一天,每天早晨至少要获得满足当天需求的赶紧餐巾,干净餐巾可以从快洗部或慢洗部获得,也可以直接买;每天晚上要决定脏餐巾的去处。每个状态有多种选择的问题,可以考虑分层图最短路,然而,对于此题,按照最短路的思想难以完成建图的工作;要使 N N N 天内每一天都满足餐巾的使用需求,且要求费用最小,不妨进一步考虑最小费用最大流。
不妨就将 N N N 天作为 N N N 个节点,再考虑早晨和晚上的不同分工,就将每个点拆成代表【早晨,夜晚】的两个点。规定:代表早晨的点编号为 1 ∼ N 1\sim N 1 ∼ N ,代表夜晚的点编号为 N + 1 ∼ 2 N N+1\sim 2N N + 1 ∼ 2 N ,源点 source \text{source} source 的编号为 0 0 0 ,汇点 sink \text{sink} sink 的编号为 2 N + 1 2N+1 2 N + 1 。
编号为 1 ∼ N 1\sim N 1 ∼ N 节点的入边用于接受干净的餐巾,包括从慢洗部、快洗部洗好的餐巾,和之间买来的毛巾:其中一部分入边为源点向 1 ∼ N 1\sim N 1 ∼ N 节点的连边,容量为 + ∞ +\infty + ∞ ,单位费用为 p p p ,这些边用于供给干净的餐巾;另一部分为代表夜晚节点的出边,将脏餐巾送到快洗部属于夜晚的操作,会连向 m m m 天后的早晨,费用为 f f f ,将脏餐巾送到慢洗部也是夜晚的操作,连向 n n n 天后的早晨,费用为 s s s 。编号为 1 ∼ N 1\sim N 1 ∼ N 节点的出边都连向汇点,容量为 r i r_i r i ,费用为 0 0 0 。
编号为 N + 1 ∼ 2 N N+1\sim 2N N + 1 ∼ 2 N 的节点入边用于接受脏的餐巾:一部分入边的另一端为源点,这些边用于提供脏餐巾,容量为 r i r_i r i (接受的仅仅是当天产生的脏餐巾),费用为 0 0 0 ;另一部分入边的另一端是前几天的夜晚,这些边提供前几天夜晚遗留下的脏餐巾,容量为 + ∞ +\infty + ∞ ,费用为 0 0 0 。编号为 N + 1 ∼ 2 N N+1\sim 2N N + 1 ∼ 2 N 的节点的出边用于处理脏毛巾:将脏餐巾送到快洗部属于夜晚的操作,会连向m m m 天后的早晨,费用为 f f f ,将脏餐巾送到慢洗部也是夜晚的操作,连向 n n n 天后的早晨,费用为 s s s 。编号为 1 ∼ N 1\sim N 1 ∼ N 节点的出边都连向汇点,容量为 r i r_i r i ,费用为 0 0 0 。
按照上述方式建图,其最大流必为 ∑ i = 1 N r i \sum\limits_{i=1}^N r_i 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 #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 ); 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 ; 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; }