题目描述

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

题目分析

费用流
S向每个月连容量inf 费用d[i]的边
除了最后一个月 每个月向下一个月连 容量为仓库容量 费用为存贮费用的边
每个月向T连容量为u[i] 费用为0 的边

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,s,t;
int head[10000],to[100000],val[100000],net[100000],flo[100000];
int tot=1;
int path[100000];
void add(int x,int y,int v,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,flo[tot]=v,val[tot]=c;
    net[++tot]=head[y];head[y]=tot,to[tot]=x,flo[tot]=0,val[tot]=-c;
}
int dis[10000],vis[10000];
int spfa()
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>q;
    vis[s]=1,q.push(s),dis[s]=0;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        vis[nmp]=0;
        for(int i=head[nmp];i;i=net[i])
            if(flo[i]>0&&dis[to[i]]>dis[nmp]+val[i])
            {
                dis[to[i]]=dis[nmp]+val[i];
                path[to[i]]=i^1;
                if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
            }
    }
    return dis[t]<0x3f3f3f3f;
}
int mincost()
{
    int ans=0;
    while(spfa())
    {
        int minflow=1<<30;
        for(int i=t;i!=s;i=to[path[i]]) minflow=min(minflow,flo[path[i]^1]);
        for(int i=t;i!=s;i=to[path[i]])
        {
            flo[path[i]]+=minflow;
            flo[path[i]^1]-=minflow;
            ans+=val[path[i]^1]*minflow;
        }
    }
    return ans;
}
int k;
int a[100],b[100];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    s=0,t=n+1;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++) add(s,i,1<<30,b[i]);
    for(int i=1;i<n;i++) add(i,i+1,k,m);
    for(int i=1;i<=n;i++) add(i,t,a[i],0);
    printf("%d",mincost());
    return 0;
}