BZOJ 2424: [HAOI2010]订货费用流

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 8
1 2 4

Sample Output

HINT

///meek

#include<bits/stdc++.h>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

const int MAXN = ;

const int MAXM = ;

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-1

void init(int n)

{

    N = n;

    tol = ;

    memset(head,-,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 = ;

    edge[tol].next = head[u];

    head[u] = tol++;

    edge[tol].to = u;

    edge[tol].cap = ;

    edge[tol].cost = -cost;

    edge[tol].flow = ;

    edge[tol].next = head[v];

    head[v] = tol++;

}

bool spfa(int s,int t)

{

    queue<int>q;

    for(int i = ;i < N;i++)

    {

        dis[i] = INF;

        vis[i] = false;

        pre[i] = -;

    }

    dis[s] = ;

    vis[s] = true;

    q.push(s);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = head[u]; i != -;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] == -)return false;

    else return true;

}

//返回的是最大流，cost存的是最小费用

int minCostMaxflow(int s,int t,int &cost)

{

    int flow = ;

    cost = ;

    while(spfa(s,t))

    {

        int Min = INF;

        for(int i = pre[t];i != -;i = pre[edge[i^].to])

        {

            if(Min > edge[i].cap - edge[i].flow)

                Min = edge[i].cap - edge[i].flow;

        }

        for(int i = pre[t];i != -;i = pre[edge[i^].to])

        {

            edge[i].flow += Min;

            edge[i^].flow -= Min;

            cost += edge[i].cost * Min;

        }

        flow += Min;

    }

    return flow;

}

const int maxn=+;

const int inff=;

int main()

{

    int n,m,S;

    scanf("%d%d%d",&n,&m,&S);

    int beg=,ends=,x;

    init();

    for(int i=;i<=n;i++) {

        scanf("%d",&x);

        add(i,ends,x,);

    }

    for(int i=;i<=n;i++) {

        scanf("%d",&x);

        add(,i,inff,x);

    }

    for(int i=;i<n;i++) { add(i,i+,S,m); }

    int ans=;

    minCostMaxflow(,ends,ans);

    cout<<ans<<endl;

    return ;

}

代码

订货