题目描述：
一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri 块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn天( n>mn>m ),其费用为 ss 分( s<fs<f )。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
建模：
把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。从S向每个Xi连一条容量为ri，费用为0的有向边。从每个Yi向T连一条容量为ri，费用为0的有向边。从S向每个Yi连一条容量为无穷大，费用为p的有向边。从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边。从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边。求网络最小费用最大流，费用流值就是要求的最小总花费。
代码：
1 #include<bits/stdc++.h>
2 #define INF 2147483647
3 #define LL long long
4 using namespace std;
5 queue<
int>
f;
6 int n,m,m1,t1,m2,t2,len=-
1,st,ed;
7 struct node{
int x,y,c,d,next;} a[
100000];
8 int b[
100000],last[
100000],pre[
100000],pos[
100000],p[
100000];
9 LL dis[
100000];
10 bool bz[
100000];
11 void ins(
int x,
int y,
int c,
int d)
12 {
13 a[++len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;a[len].next=last[x];last[x]=
len;
14 a[++len].x=y;a[len].y=x;a[len].c=
0;a[len].d=-d;a[len].next=last[y];last[y]=
len;
15 }
16 bool spfa()
17 {
18 memset(bz,
true,
sizeof(bz));
19 bz[st]=
false;
20 memset(dis,
63,
sizeof(dis));
21 dis[st]=
0;
22 p[st]=
INF;
23 f.push(st);
24 while(!
f.empty())
25 {
26 int x=
f.front();
27 bz[x]=
true;
28 for(
int i=last[x];i>-
1;i=
a[i].next)
29 {
30 int y=
a[i].y;
31 if(a[i].c>
0&&dis[y]>dis[x]+
a[i].d)
32 {
33 dis[y]=dis[x]+
a[i].d;
34 pos[y]=
x;
35 pre[y]=
i;
36 p[y]=
min(p[x],a[i].c);
37 if(bz[y])
38 {
39 f.push(y);
40 bz[y]=
false;
41 }
42 }
43 }
44 f.pop();
45 }
46 return dis[ed]<
4557430888798830399;
47 }
48 LL flow()
49 {
50 LL ans=
0;
51 while(spfa())
52 {
53 ans+=p[ed]*
dis[ed];
54 for(
int i=ed;i!=st;i=
pos[i])
55 {
56 a[pre[i]].c-=
p[ed];
57 a[pre[i]^
1].c+=
p[ed];
58 }
59 }
60 return ans;
61 }
62 int main()
63 {
64 int x;
65 scanf(
"%d",&
n);
66 st=
0,ed=
2*n+
1;
67 memset(last,-
1,
sizeof(last));
68 for(
int i=
1;i<=n;i++
)
69 {
70 scanf(
"%d",&
x);
71 ins(st,i,x,
0);
//每天晚上从起点获得x条脏餐巾
72 ins(i+n,ed,x,
0);
//每天白天,向汇点提供x条干净的餐巾,流满时表示第i天的餐巾够用
73 }
74 scanf(
"%d %d %d %d %d",&m,&t1,&m1,&t2,&
m2);
75 for(
int i=
1;i<=n;i++
)
76 {
77 if(i+
1<=n) ins(i,i+
1,INF,
0);
//每天晚上可以将脏餐巾留到第二天晚上
78 if(i+t1<=n) ins(i,i+n+t1,INF,m1);
//每天晚上可以送去快洗部,在地i+t1天早上收到餐巾
79 if(i+t2<=n) ins(i,i+n+t2,INF,m2);
//每天晚上可以送去慢洗部,在地i+t2天早上收到餐巾
80 ins(st,i+n,INF,m);
//每天早上可以购买餐巾
81 }
82 printf(
"%lld",flow());
83 }
View Code
转载于:https://www.cnblogs.com/71-111/p/9337769.html
