2424: [HAOI2010]订货
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 81 2 4Sample Output
34
HINT
///meek#includeusing namespace std ;typedef long long ll;#define mem(a) memset(a,0,sizeof(a))#define pb push_backconst int MAXN = 10000;const int MAXM = 100000;const int INF = 0x3f3f3f3f;struct Edge{ int to,next,cap,flow,cost;}edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int N;//节点总个数，节点编号从0~N-1void init(int n){ N = n; tol = 0; memset(head,-1,sizeof(head));}void add(int u,int v,int cap,int cost) //点u至点v,容量，花费{ edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++;}bool spfa(int s,int t){ queue q; for(int i = 0;i < N;i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i != -1;i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(pre[t] == -1)return false; else return true;}//返回的是最大流，cost存的是最小费用int minCostMaxflow(int s,int t,int &cost){ int flow = 0; cost = 0; while(spfa(s,t)) { int Min = INF; for(int i = pre[t];i != -1;i = pre[edge[i^1].to]) { if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for(int i = pre[t];i != -1;i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow;}const int maxn=100000+50;const int inff=1000000000;int main(){ int n,m,S; scanf("%d%d%d",&n,&m,&S); int beg=0,ends=3000,x; init(10000); for(int i=1;i<=n;i++) { scanf("%d",&x); add(i,ends,x,0); } for(int i=1;i<=n;i++) { scanf("%d",&x); add(0,i,inff,x); } for(int i=1;i