Description

某公司估计市场在第 \(i\) 个月对某产品的需求量为 \(U_i\), 已知在第 \(i\) 月该产品的订货单价为 \(d_i\), 上个月月底未销完的单位产品要付存贮费用 \(m\), 假定第一月月初的 库存量为零, 第 \(n\) 月月底的库存量也为零, 问如何安排这 \(n\) 个月订购计划, 才能使成本最低? 每月月初订购, 订购后产品立即到货, 进库并供应市场, 于当月被售掉则不必付 存贮费. 假设仓库容量为 \(S\).

Input

第 1 行:\(n, m, S (0 \leq n \leq 50, 0 \leq m \leq 10, 0 \leq S \leq 10000\)

第 2 行:\(U_1, U_2, \ldots, U_i, \ldots, U_n (0 \leq U_i \leq 10000)\)

第 3 行:\(d_1, d_2, \ldots, d_i, \ldots, d_n (0 \leq d_i \leq 100)\)

Output

只有 \(1\) 行, 一个整数, 代表最低成本

Sample Input

3 1 1000
2 4 8
1 2 4

Sample Output

34

Explanation

更裸的一道费用流 (数据还弱)

如果用动规你就挂菜了, 因为时间复杂度是 \(O(n^2 \cdot S^2)\), 报表没商量

其实就是带权限流

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 100, maxm = 500;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class MaxFlowMinCost
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    lli dist[maxn];
    edge *edges[maxn], epool[maxm], *from[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool inque[maxn];
    bool spfa(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            inque[i] = false, dist[i] = infinit, from[i] = NULL;
        que.push(s);
        inque[s] = true, dist[s] = 0;
        while (!que.empty()) {
            int p =que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            inque[p] = false;
        }
        if (dist[t] >= infinit)
            return false;
        return true;
    }
    lli max_flow, min_cost;
    void eval(void)
    {
        max_flow = 0;
        min_cost = 0;
        while (spfa()) {
            lli tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                ep->flow -= tmp,
                ep->rev->flow += tmp;
            max_flow += tmp;
            min_cost += tmp * dist[t];
        }
        return ;
    }
} graph;

int n, m, S;
int U[maxn], d[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &S);
    graph.n = n + 2;
    graph.s = n + 1;
    graph.t = n + 2;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &U[i]);
        graph.add_edge(i, graph.t, U[i], 0);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &d[i]);
        graph.add_edge(graph.s, i, infinit, d[i]);
    }
    for (int i = 1; i <= n - 1; i++) {
        graph.add_edge(i, i + 1, S, m);
    }
    graph.eval();
    lli res = graph.min_cost;
    printf("%lld\n", res);
    return 0;
}