11/14
22:17
OI

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

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)

#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;
}