首页 > 代码库 > 线性规划与网络流10 餐巾计划问题
线性规划与网络流10 餐巾计划问题
算法实现题 8-10 餐巾计划问题（习题 8-21）
?问题描述：
一个餐厅在相继的 N 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri块餐巾(i=1，
2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为 p 分；或者把旧餐巾送到快洗部，
洗一块需 m 天，其费用为 f 分；或者送到慢洗部，洗一块需 n 天(n>m)，其费用为 s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多
少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划，使总的花费最小。
?编程任务：
编程找出一个最佳餐巾使用计划.
?数据输入：
由文件 input.txt 提供输入数据。文件第 1 行有 6 个正整数 N,p,m,f,n,s。N 是要安排餐巾
使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗
一块餐巾需要的费用；n 是慢洗部洗一块餐巾需用天数；s 是慢洗部洗一块餐巾需要的费用。
接下来的 N 行是餐厅在相继的 N 天里，每天需用的餐巾数。
?结果输出:
程序运行结束时，将餐厅在相继的 N 天里使用餐巾的最小总花费输出到文件 output.txt
中。
输入文件示例
输出文件示例
input.txt
output.txt
3 10 2 3 3 2
5
6
7
145
题解：
其实构图不难想，关键在于细节的处理-----边的容量设置
而且还要注意读题，题中说可以延期洗，所以应该从i到i+1连一条容量为inf的边，inf是因为有可能积淀了好几天
注意到这一点后，同理 i 向 i+t1+n 连边的容量也需要时inf，i+t2+n 的容量也是inf
其实这题和saveprint那题有点像，构图都是比较巧妙的
代码：
1 uses math; 2 const inf=maxlongint; 3 type node=record 4 from,go,next,v,c:longint; 5 end; 6 var e:array[0..2000000] of node; 7 pre,head,q,d:array[0..1000000] of longint; 8 v:array[0..1000000] of boolean; 9 i,j,n,s,t,l,r,mincost,tot,p,t1,t2,p1,p2,x:longint; 10 procedure ins(x,y,z,w:longint); 11 begin 12 inc(tot); 13 with e[tot] do 14 begin 15 from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot; 16 end; 17 end; 18 procedure insert(x,y,z,w:longint); 19 begin 20 ins(x,y,z,w);ins(y,x,0,-w); 21 end; 22 function spfa:boolean; 23 var i,x,y:longint; 24 begin 25 fillchar(v,sizeof(v),false); 26 for i:=s to t do d[i]:=inf; 27 l:=0;r:=1;q[1]:=s;d[s]:=0;v[s]:=true; 28 while l<r do 29 begin 30 inc(l); 31 x:=q[l];v[x]:=false; 32 i:=head[x]; 33 while i<>0 do 34 begin 35 y:=e[i].go; 36 if (e[i].v<>0) and (d[x]+e[i].c<d[y]) then 37 begin 38 d[y]:=d[x]+e[i].c; 39 pre[y]:=i; 40 if not(v[y]) then 41 begin 42 v[y]:=true; 43 inc(r); 44 q[r]:=y; 45 end; 46 end; 47 i:=e[i].next; 48 end; 49 end; 50 exit(d[t]<>inf); 51 end; 52 procedure mcf; 53 var i,tmp:longint; 54 begin 55 mincost:=0; 56 while spfa do 57 begin 58 tmp:=inf; 59 i:=pre[t]; 60 while i<>0 do 61 begin 62 tmp:=min(tmp,e[i].v); 63 i:=pre[e[i].from]; 64 end; 65 inc(mincost,tmp*d[t]); 66 i:=pre[t]; 67 while i<>0 do 68 begin 69 dec(e[i].v,tmp); 70 inc(e[i xor 1].v,tmp); 71 i:=pre[e[i].from]; 72 end; 73 end; 74 end; 75 procedure init; 76 begin 77 tot:=1; 78 readln(n,p,t1,p1,t2,p2); 79 s:=0;t:=2*n+1; 80 for i:=1 to n do 81 begin 82 readln(x); 83 insert(s,i,x,0); 84 insert(s,i+n,x,p); 85 insert(i+n,t,x,0); 86 if i+1<=n then insert(i,i+1,inf,0); 87 if i+t1<=n then insert(i,i+t1+n,inf,p1); 88 if i+t2<=n then insert(i,i+t2+n,inf,p2); 89 end; 90 end; 91 procedure main; 92 begin 93 mincost:=0; 94 mcf; 95 writeln(mincost); 96 end; 97 begin 98 assign(input,‘input.txt‘);assign(output,‘output.txt‘); 99 reset(input);rewrite(output);100 init;101 main;102 close(input);close(output);103 end.