首页 > 代码库 > bzoj2424: [HAOI2010]订货
bzoj2424: [HAOI2010]订货
2424: [HAOI2010]订货
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 836 Solved: 586
[Submit][Status][Discuss]
Description
某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为S。
Input
第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)
Output
只有1行,一个整数,代表最低成本
Sample Input
3 1 1000
2 4 8
1 2 4
2 4 8
1 2 4
Sample Output
34
HINT
Source
Day1
跟24题的餐巾问题挺像的?
//建图具体还是看代码吧...(懒
似乎只有我拆点了?
1 #include<bits/stdc++.h> 2 #define inf 2147483647 3 #define rep(i,l,r) for(int i=l;i<=r;i++) 4 #define N 1000 5 using namespace std; 6 struct Edge{ 7 int to,next,from,c,w; 8 }e[100000]; 9 int head[N],tot=1,ans,dis[N],from[N],r[N],n,T,a,m,S;10 bool used[N];11 inline void ins(int u,int v,int w,int cost) {12 e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].c=cost; e[tot].from=u;13 }14 inline void insert(int u,int v,int w,int cost) {15 ins(u,v,w,cost); ins(v,u,0,-cost);16 }17 inline bool spfa() {18 queue<int> q; for(int i=0;i<=T;i++) dis[i]=inf; dis[0]=0; q.push(0); used[0]=1; 19 while(!q.empty()) {20 int x=q.front(); q.pop();21 for(int k=head[x];k;k=e[k].next) 22 if(e[k].w>0&&dis[x]+e[k].c<dis[e[k].to]){23 dis[e[k].to]=dis[x]+e[k].c; from[e[k].to]=k;24 if(!used[e[k].to]) {25 used[e[k].to]=1; q.push(e[k].to);26 }27 }28 used[x]=0;29 }30 if(dis[T]==inf) return 0;else return 1;31 }32 33 inline void run() {34 int x=inf;35 for(int k=from[T];k;k=from[e[k].from]) x=min(x,e[k].w);36 for(int k=from[T];k;k=from[e[k].from]) {37 e[k].w-=x; e[k^1].w+=x; ans+=e[k].c*x;38 }39 }40 int main () {41 scanf("%d%d%d",&n,&m,&S);42 T=n+n+1;43 rep(i,1,n) scanf("%d",&a),insert(i+n,T,a,0);44 rep(i,1,n) scanf("%d",&a),insert(0,i,inf,a);45 rep(i,1,n) insert(i,i+n,inf,0);46 rep(i,1,n-1) insert(i+n,i+1,S,m);47 while(spfa()) run();48 printf("%d",ans);49 }
bzoj2424: [HAOI2010]订货
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。