BZOJ-2424: [HAOI2010]订货【费用流】

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

HINT

Source

Day1

思路：建立超级源和超级汇，令每条连向超级汇的边代价为0、cap为当月需求量，连向超级源的边cap无穷大，代价为当月进货价，每月之间连的边cap为仓库容量，代价为每天贮存花销。

建图后跑MCMF

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = ;

const int inf  = 0x3f3f3f3f;

int n,m,s;

int cnt = ;

int ans;

int from[],q[],dis[],head[];

bool inq[];

template<class T>inline void read(T &res)

{

    char c;T flag=;

    while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';

    while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;

}

struct node {

    int from,to,next,v,c;

}e[];

void add(int u,int v,int w,int c)

{

    cnt++;

    e[cnt].from = u;

    e[cnt].to   = v;

    e[cnt].v    = w;

    e[cnt].c    = c;

    e[cnt].next = head[u];

    head[u]     = cnt;

}

void BuildGraph(int u,int v,int w,int c)

{

    add(u,v,w,c);

    add(v,u,,-c);///反向

}

bool spfa()

{

    for(int i = ; i <= maxn; i++)dis[i]=inf;

    int t = , w = , now;

    dis[] = q[] = ;

    inq[] = ;

    while(t != w) {

        now = q[t];

        t++;

        if(t == maxn) t = ;

        for(int i = head[now]; i; i = e[i].next) {

            if(e[i].v && dis[e[i].to] > dis[now] + e[i].c) {

                from[e[i].to] = i;

                dis[e[i].to]  = dis[now] + e[i].c;

                if(!inq[e[i].to]) {

                    inq[e[i].to] = ;

                    q[w++] = e[i].to;

                    if(w == maxn) w = ;

                }

            }

        }

        inq[now] = ;

    }

    if(dis[maxn] == inf)

        return ;

    return ;

}

void mcmf()///最小费用最大流

{

    int i;

    int x = inf;

    i = from[maxn];

    while(i) {

        x = min(e[i].v,x);

        i = from[e[i].from];

    }

    i = from[maxn];

    while(i) {

        e[i].v   -= x;

        e[i^].v += x;

        ans += x * e[i].c;

        //printf("ans : %d\n",ans);

        i    = from[e[i].from];

    }

}

int main()

{

    read(n),read(m),read(s);

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

        int u;

        read(u);

        BuildGraph(i, maxn, u, );

    }

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

        int d;

        read(d);

        BuildGraph(, i, inf, d);

    }

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

        BuildGraph(i, i+, s, m);

    }

    while(spfa()) {

        mcmf();

    }

    printf("%d",ans);

    return ;

}

秒客网