「网络流24题」餐巾计划问题
题目描述 Description
一个餐厅在相继的 N 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为 p 分；或者把旧餐巾送到快洗部，洗一块需 m 天，其费用为 f 分；或者送到慢洗部，洗一块需 n 天(n>m)，其费用为 s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划，使总的花费最小。
编程找出一个最佳餐巾使用计划.
输入描述 Input Description
第 1 行有 6 个正整数 N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n 是慢洗部洗一块餐巾需用天数；s 是慢洗部洗一块餐巾需要的费用。接下来的 N 行是餐厅在相继的 N 天里，每天需用的餐巾数。
输出描述 Output Description
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
样例输入 Sample Input
3 10 2 3 3 2
5
6
7
样例输出 Sample Output
145
题解
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m)，费用为f，送到慢洗部(Xi->Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。
|
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 |
#include<iostream> #include<cstdio> #define inf 0x7fffffff #define T 2001 using namespace std; int cnt=1,day,p,m,f,n,s,ans; int from[2005],q[2005],dis[2005],head[2005]; bool inq[2005]; struct data{int from,to,next,v,c;}e[1000001]; void ins(int u,int v,int w,int c) { cnt++; e[cnt].from=u;e[cnt].to=v; e[cnt].v=w;e[cnt].c=c; e[cnt].next=head[u];head[u]=cnt; } void insert(int u,int v,int w,int c) {ins(u,v,w,c);ins(v,u,0,-c);} bool spfa() { for(int i=0;i<=T;i++)dis[i]=inf; int t=0,w=1,i,now; dis[0]=q[0]=0;inq[0]=1; while(t!=w) { now=q[t];t++;if(t==2001)t=0; for(int i=head[now];i;i=e[i].next) { if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c) { from[e[i].to]=i; dis[e[i].to]=dis[now]+e[i].c; if(!inq[e[i].to]) { inq[e[i].to]=1; q[w++]=e[i].to; if(w==2001)w=0; } } } inq[now]=0; } if(dis[T]==inf)return 0;return 1; } void mcf() { int i,x=inf; i=from[T]; while(i) { x=min(e[i].v,x); i=from[e[i].from]; } i=from[T]; while(i) { e[i].v-=x; e[i^1].v+=x; ans+=x*e[i].c; i=from[e[i].from]; } } int main() { scanf("%d%d%d%d%d%d",&day,&p,&m,&f,&n,&s); for(int i=1;i<=day;i++) { if(i+1<=day)insert(i,i+1,inf,0); if(i+m<=day)insert(i,day+i+m,inf,f); if(i+n<=day)insert(i,day+i+n,inf,s); insert(0,day+i,inf,p); } int x; for(int i=1;i<=day;i++) { scanf("%d",&x); insert(0,i,x,0); insert(day+i,T,x,0); } while(spfa())mcf(); printf("%d",ans); return 0; } |
OI 课件=>
