基础最优化练习题 费用流贪心

发表于 更新于 分类于 阅读次数：

P5653 基础最优化练习题 很不错的贪心题. $$ans = \sum_{i=1}^n b_i w_i $$ $$=\sum_{i=1}^n \Delta b_i \sum_{j=i}^n w_j$$ 记录$w$的后缀和$s$,然后建立费用流模型: 对于$i \in [1,n]$,和源点汇点都连边,然后两个点之间连边是$a$ 显然这张图的最小费用就是答案 考虑用堆模拟费用流 一个一个点的考虑,如果被$a$限制,则考虑退流,选择之前费用最小的一条边退即可 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e6 + 233;
typedef long long ll;
int n, m, a[N], w[N];
ll s[N], ans;

struct Node {
  int flow;
  ll cost;
};

bool operator<(const Node &a, const Node &b) {
  return a.cost > b.cost;
}

std::priority_queue<Node> que;

int main() {
  n = rd(), m = rd();
  for (int i = 1; i <= n; ++i)
    a[i] = rd();
  for (int i = 1; i <= n; ++i)
    w[i] = rd();
  for (int i = n; i; --i)
    s[i] = s[i + 1] + w[i];

  for (int i = 1, now = 0; i <= n; ++i) {
    if (s[i] > 0) {
      ans += m * s[i];
      que.push({ m * 2, s[i] });
      now += m;
    } else {
      ans -= m * s[i];
      now -= m;
    }
    int c = now - a[i];
    now = std::min(now, a[i]);
    while (c > 0 && !que.empty()) {
      Node node = que.top();
      que.pop();
      int tmp = std::min(c, node.flow);
      ans -= tmp * node.cost;
      c -= tmp;
      node.flow -= tmp;
      if (node.flow)
        que.push(node);
    }
  }

  std::cout << ans << std::endl;
  return 0;
}