题目描述
某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为S。
输入格式
第1行:n, m, S (0<=n<=50, 0<=m<=10, 0<=S<=10000)
第2行:U1 , U2 , ... , Ui , ... , Un (0<=Ui<=10000)
第3行:d1 , d2 , ..., di , ... , dn (0<=di<=100)
输出格式
只有1行,一个整数,代表最低成本。
题目解析
又是一发餐巾计划问题。
分析一下题目条件,建模如下:
1.按月数建点,设第
月为
。
2.建源
汇
,
向
连容量为无穷大,费用为
的边,表示该月订单。
3.
向
连容量为
,费用为0的边,表示当月的需求量。
4.
向
连容量为
,费用为
的边,表示第
月贮存下来的产品。
跑最小费用最大流即可。感觉这种类餐巾计划问题形式还是蛮统一的。
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 |
/************************************************************** Problem: 2424 User: frank_c1 Language: C++ Result: Accepted Time:12 ms Memory:1296 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to,cap,cost; }; const int maxn=60; const int INF=(int)(1e9); int fr[maxn]; edge e[maxn*20]; int d[maxn],a[maxn],p[maxn]; bool inq[maxn]; int tot,s,t,fl,cs,tote=-1; inline void addone(int u,int v,int c,int s) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].to=v; e[tote].cap=c;e[tote].cost=s; } inline void addedge(int u,int v,int c,int s) { addone(u,v,c,s);addone(v,u,0,-s); //printf("%d %d %d %d\n",u,v,c,s); } queue<int> Q; bool SPFA() { REP(i,0,tot) d[i]=INF; Q.push(s);inq[s]=1;a[s]=INF;d[s]=0; while(!Q.empty()) { int x=Q.front();Q.pop(); inq[x]=0; RAL(i,x) if(e[i].cap && d[e[i].to]>d[x]+e[i].cost) { d[e[i].to]=d[x]+e[i].cost; a[e[i].to]=min(a[x],e[i].cap); p[e[i].to]=i; if(!inq[e[i].to]) { Q.push(e[i].to); inq[e[i].to]=1; } } } if(d[t]==INF) return 0; fl+=a[t]; cs+=a[t]*d[t]; int x=t; while(x!=s) { e[p[x]].cap-=a[t]; e[p[x]^1].cap+=a[t]; x=e[p[x]^1].to; } return 1; } void mincost() { fl=cs=0;while(SPFA()); } int D[60],U[60]; int main() { int n,m,mx; read(n);read(m);read(mx); memset(fr,-1,sizeof(fr)); s=0;t=1; REP(i,1,n) read(U[i]); REP(i,1,n) read(D[i]); REP(i,1,n) { addedge(s,i+1,INF,D[i]); addedge(i+1,t,U[i],0); if(i+1<=n) addedge(i+1,i+2,mx,m); } tot=n+1;mincost(); printf("%d\n",cs); return 0; } |