首页 > 代码库 > bzoj2424: [HAOI2010]订货

bzoj2424: [HAOI2010]订货

2024-08-13 22:17:59   222人阅读

2424: [HAOI2010]订货

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 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

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 }
View Code

 

bzoj2424: [HAOI2010]订货


联系
我们