CTSC2010 产品销售

题目:

  A 公司正在热销某计算机产品,作为 A 公司 CEO 的小 A 打算为接下来连续的 个销售季度制定一份具体的生产和销售方案。 已知第 个销售季度该产品的订购量为 ,在第 个季度,A 公司会通过如下几种方式来解决用户的订购需求:
  在第 个季度生产新的产品来销售。
  若在第 个季度以前库存还有多余的产品,则可以直接在第 个季度销售(注意第一个季度之前没有任何库存产品)。
  在第 个季度可以不完成全部的订购需求,而将未完成的订购需求推迟,归入到下一个季度 的产品订购需求中。
  A 公司需要考虑以下几种耗费: 生产新产品的成本耗费、库存产品的额外储存耗费以及推迟订购需求而需要赔偿给用户的损失费。另外由于劳力和资源的限制,每个销售季度能够生产新产品的数量是有限的,各季度的耗费和可以生产的产品上限数也不尽相同,具体如下:
  在第 个季度最多可以生产 件新的产品,每一件的成本为
  第 个季度保存下来的产品,可以用于以后季度的销售。对于每一件产品,若从第 季度保存到第 季度, 需要额外支付 的存储费用(注意产品保存到下个季度后可能再次库存)。
  对于第 个季度需要推迟而归入到下一个季度订购需求的每一件产品, A 公司需要赔偿给用户损失费 (注意延迟到下个季度可能再次被延迟, 费 用按后面季度的延迟费用计)。
  在第 个季度结束后, A 公司必须解决之前所有的用户订单。可以保证, A公司能够生产的产品总数不会低于总订购量, 也就是说一定存在一组生产和销售方案使得满足所有的用户订购需求。小 A 想知道如何来安排产品的生产和销售,使得在满足所有订购需求的前提下公司总的耗费最小。

思路:

   的费用流应该还是比较简单的。
  然后我们可以观察发现,这题的图它长得很特别很别致,大概就是先有一排点用两条有向边相互连,然后从 连向这一排每一个点,每个点再连向 。比如当 时它长成这样:

20190824.png

  所以考虑利用这个图的特性,用其他办法计算费用流,也就是模拟费用流(说起来这个好像今年 WC 的时候讲了,然而我冬眠了qwq)。为了方便起见把中间那排左向右的边称作 型边,右向左称为 型边。首先 相连的边是不会产生退流的,如果从左往右去满足每条与 相连的边的流量,那么当前点右侧的 型边都还没有走过,而左侧 型边的反边也不可能去走,所以这个图中要维护的反边其实只有 型边的反边。
  因为依然维护了反边(能进行退流操作),所以求费用流的过程可以像普通的一样费用流算法一样,每次找到费用最小的路径流。
  那对于当前点右侧的点因为不存在反边,所以每个点流出时的花费是一直不变的。所以只要利用前缀和表示一下贡献,排序后从前往后取即可。
  而左侧的点可以用一棵线段树维护反边的流量,另一棵线段树也用前缀和表示贡献。因为反边的花费是负值,所以能走反边时就一定走反边。同时因为左侧的反边流量是不会增加的,所以当反边流量为 时就把代价设成 型边的花费,流量设为无穷大即可。
  每次就在左右中选一个更优的路径去流,直到当前边满流为止。因为每一次都会导致至少一条边满流,所以复杂度是

代码:

#include <bits/stdc++.h>
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1e5 + 5, S = N << 2, INF = 1e8;
struct Data {
    int val, id;
    bool operator< (const Data f) const {
        return val < f.val;
    }
};

int n;

struct Segment {
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid (L + R >> 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
    Data data[S];
    int add[S];
    void build(int a[], int o = 1, int L = 1, int R = n) {
        if(L == R) {data[o] = (Data) {a[L], L}; return;}
        build(a, lson); build(a, rson);
        data[o] = min(data[ls], data[rs]);
    }
    void down(int o) {
        if(!add[o]) return;
        data[ls].val += add[o];
        data[rs].val += add[o];
        add[ls] += add[o];
        add[rs] += add[o];
        add[o] = 0;
    }
    void upd(int l, int r, int d, int o = 1, int L = 1, int R = n) {
        if(l > r) return;
        if(L == l && R == r) {
            data[o].val += d; add[o] += d;
            return;
        }
        down(o);
        if(r <= mid) upd(l, r, d, lson);
        else if(l > mid) upd(l, r, d, rson);
        else upd(l, mid, d, lson), upd(mid + 1, r, d, rson);
        data[o] = min(data[ls], data[rs]);
    }
    Data qry(int l, int r, int o = 1, int L = 1, int R = n) {
        if(l > r) return (Data) {INF, INF};
        if(l == L && r == R) return data[o];
        down(o);
        if(r <= mid) return qry(l, r, lson);
        else if(l > mid) return qry(l, r, rson);
        else return min(qry(l, mid, lson), qry(mid + 1, r, rson));
    }
} seg1, seg2;

Data dt[N];

int D[N], U[N], P[N], M[N], C[N];
int spre[N], snxt[N], tmp[N];

int main() {
    File(product);
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", D + i);
    rep(i, 1, n) scanf("%d", U + i);
    rep(i, 1, n) scanf("%d", P + i);
    rep(i, 1, n - 1) scanf("%d", M + i);
    rep(i, 1, n - 1) scanf("%d", C + i);
    seg1.build(tmp);

    rep(i, 1, n - 1) spre[i] = spre[i - 1] + C[i];
    drep(i, n - 1, 1) snxt[i] = snxt[i + 1] + C[i];
    rep(i, 1, n) tmp[i] = P[i] - snxt[i];
    seg2.build(tmp);

    rep(i, 1, n) dt[i] = (Data) {spre[i - 1] + P[i], i};
    sort(dt + 1, dt + 1 + n);
    int hed = 1;
    ll ans = 0;
    rep(i, 1, n) while(D[i]) {
        Data d;
        while((d = seg1.qry(1, i - 1)).val == 0) {
            seg1.upd(d.id, d.id, INF);
            seg2.upd(1, d.id, C[d.id] + M[d.id]);
        }
        while(hed <= n && (dt[hed].id <= i || U[dt[hed].id] == 0)) hed++;
        d = seg2.qry(1, i);
        int val1 = d.val + snxt[i];
        int val2 = (hed <= n ? dt[hed].val - spre[i - 1] : 1e9);
        if(val1 < val2) {
            int id = d.id;
            int flow = min3(U[id], seg1.qry(id, i - 1).val, D[i]);
            seg1.upd(id, i - 1, -flow);
            if((U[id] -= flow) == 0) seg2.upd(id, id, INF);
            D[i] -= flow; ans += (ll) flow * val1;
        }
        else {
            int id = dt[hed].id;
            int flow = min(U[id], D[i]);
            seg1.upd(i, id - 1, flow);
            if((U[id] -= flow) == 0) seg2.upd(id, id, INF);
            D[i] -= flow; ans += (ll) flow * val2;
        }
    }
    printf("%lld\n", ans);
    return 0;
}