本题唯一难点是读对题。

Missa · 2024-02-18 09:44:27 · 题解

如果你没有读错题，想必 20min 就够了。可惜这个人读错了两处题意浪费了 10min 导致没写完 G，这就是另一个故事了。

首先思考为什么这个过程会结束，发现有 w_i 的限制。考虑 \sum a_iw_i，每次操作这个数值严格减小，因此操作数目的上限即为 \sum a_iw_i。

注意到一枚硬币只会从 w 大的地方到达 w 小的地方，因此按 w 从大到小做背包，求出 g_u 表示在 u 处放置一个硬币最多能进行下去几次操作，转移时做 01 背包即可。复杂度 O(nm)，因为所有点一共有 2m 个邻居。

#include <bits/stdc++.h>

int main() {
  int n, m; scanf("%d %d", &n, &m);
  std::vector<std::vector<int>> e(n);
  for (int i = 0, u, v; i < m; i++) {
    scanf("%d %d", &u, &v), --u, --v;
    e[u].push_back(v), e[v].push_back(u);
  }
  int mx(1);
  std::vector<int> w(n), a(n), id(n);
  for (int &x : w) scanf("%d", &x), mx = std::max(mx, x);
  std::iota(id.begin(), id.end(), 0);
  std::sort(id.begin(), id.end(), [&](int x, int y) -> bool {
    return w[x] < w[y];
  });
  std::vector<int> g(n);
  for (int &u : id) {
    std::vector<int> f(w[u], 1);
    for (int v : e[u]) {
      int t = w[v];
      for (int i = w[u] - 1; i >= t; i--)
        f[i] = std::max(f[i], f[i - t] + g[v]);
    }
    g[u] = *std::max_element(f.begin(), f.end());
  }
  long long ans(0);
  for (int i = 0, x; i < n; i++) {
    scanf("%d", &x);
    ans += 1ll * x * g[i];
  }
  printf("%lld\n", ans);
}