BZOJ2424 [HAOI2010] 订货

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2424

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行，一个整数，代表最低成本

建图很容易，简直就是裸题，乱搞即可。

别人的代码跑得比香港记者还快，0ms跑完，我的还要4500ms……

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 6 #define rep(i,l,r) for(int i=l; i<=r; i++)
 7 #define clr(x,y) memset(x,y,sizeof(x))
 8 #define travel(x) for(Edge *p=last[x]; p; p=p->pre)
 9 using namespace std;
10 const int INF = 0x3f3f3f3f;
11 const int maxn = 60;
12 inline int read(){
13     int ans = 0, f = 1;
14     char c = getchar();
15     for(; !isdigit(c); c = getchar())
16     if (c == '-') f = -1;
17     for(; isdigit(c); c = getchar())
18     ans = ans * 10 + c - '0';
19     return ans * f;
20 }
21 struct Edge{
22     Edge *pre,*rev; int to,cap,cost;
23 }edge[maxn*6],*last[maxn],*pre[maxn],*pt;
24 int n,m,s,S,T,x,d[maxn];
25 bool isin[maxn];
26 queue <int> q;
27 inline void add(int x,int y,int z,int w){
28     pt->pre = last[x]; pt->to = y; pt->cap = z; pt->cost = w; last[x] = pt++;
29     pt->pre = last[y]; pt->to = x; pt->cap = 0; pt->cost = -w; last[y] = pt++;
30     last[x]->rev = last[y]; last[y]->rev = last[x];
31 }
32 bool spfa(){
33     clr(isin,0); isin[S] = 1; q.push(S);
34     clr(d,INF); d[S] = 0;
35     while (!q.empty()){
36         int now = q.front(); q.pop(); isin[now] = 0;
37         travel(now){
38             if (d[p->to] > d[now] + p->cost && p->cap > 0){
39                 d[p->to] = d[now] + p->cost;
40                 pre[p->to] = p;
41                 if (!isin[p->to]) isin[p->to] = 1, q.push(p->to);
42             }
43         }
44     }
45     return d[T] != INF;
46 }
47 int mincost(){
48     int x = INF, cost = 0;
49     while (spfa()){
50         for(Edge *p = pre[T]; p; p = pre[p->rev->to]) x = min(x,p->cap);
51         for(Edge *p = pre[T]; p; p = pre[p->rev->to]){
52             cost += x * p->cost; p->cap -= x; p->rev->cap += x;
53         }
54     }
55     return cost;
56 }
57 int main(){
58     n = read(); m = read(); s = read();
59     S = 0; T = n + 1; clr(last,0); pt = edge;
60     rep(i,1,n) x = read(), add(i,T,x,0);
61     rep(i,1,n) x = read(), add(S,i,INF,x);
62     rep(i,1,n-1) add(i,i+1,s,m);
63     printf("%d
",mincost());
64     return 0;
65 }

View Code