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 = 2001;  const int inf  = 0x3f3f3f3f;  int n,m,s;  int cnt = 1;  int ans;  int from[2005],q[2005],dis[2005],head[2005]; bool inq[2005];

template<class T>inline void read(T &res)
{ char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
} struct node { int from,to,next,v,c;
}e[1000001]; 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,0,-c);///反向 } bool spfa()
{ for(int i = 0; i <= maxn; i++)dis[i]=inf; int t = 0, w = 1, now;
    dis[0] = q[0] = 0;
    inq[0] = 1; while(t != w) {
        now = q[t];
        t++; if(t == maxn) t = 0; 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] = 1;
                    q[w++] = e[i].to; if(w == maxn) w = 0;
                }
            }
        }
        inq[now] = 0;
    } if(dis[maxn] == inf) return 0; return 1;
} 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^1].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 = 1; i <= n; i++) { int u;
        read(u);
        BuildGraph(i, maxn, u, 0);
    } for(int i = 1; i <= n; i++) { int d;
        read(d);
        BuildGraph(0, i, inf, d);
    } for(int i = 1; i < n; i++) {
        BuildGraph(i, i+1, s, m);
    } while(spfa()) {
        mcmf();
    }
    printf("%d",ans); return 0;
}