QOJ #6406. Stage Clear 题解

Description

陈教授非常喜欢玩电脑游戏。他现在正在游戏中与可怕的怪物战斗。

战场由 $n$ 个交叉点组成，编号为 1 到 $n$。这些交叉点之间有 $m$ 条有向边，因此整个战场可以被看作一个有向无环图（DAG）。玩家现在处在交叉点 1，并拥有 $X$ 点生命值（HP）。

除了交叉点 1，每个交叉点上都有一个怪物。当玩家第一次移动到某个交叉点时，必须与该交叉点上的怪物战斗。在战斗中，玩家会损失 $a_i$ 点 HP，而在击败怪物后，他会获得 $b_i$ 点 HP。注意：一旦 HP 变成负数（< 0），游戏就会失败，所以必须确保这种情况绝不会发生。

如果玩家多次访问同一个交叉点，战斗只会在第一次发生——怪物不会复活。玩家只能沿着给定的 $m$ 条有向边移动，或者通过魔法飞回交叉点 1。飞行可以进行多次。

此外，从交叉点 1 总是可以到达任意一个交叉点。

当所有怪物都被击败后，陈教授就可以通过这一关卡。

请你编写一个程序，计算出通关所需的最小初始生命值 HP（即最小的 $X$）。

$n+m\leq 72,m\geq n-1$。

Solution

首先 $n\leq 25$ 时可以暴力状压 dp 做到 $O(2^nn)$。

对于 $n>25$，$m\leq 72-n=46$，此时 $m-n$ 比较小，很容易想到这是 dfs 树上非树边的数量。

注意到操作的过程类似一棵树，即一个点的父亲选了，这个点才能选，所以考虑暴力枚举出每个点的父亲，这是 $O(2^{m-n+1})$ 级别的。

剩下的部分形如：·给定一棵树，一个点的父亲选了，这个点才能选，问最小初始生命值。

这是个比较经典的贪心问题，先不管父亲的限制，通过排序得到一个最优的顺序。

设最优顺序中第一个是 $u$，那么当 $u$ 的父亲选了后一定贪心地选 $u$，所以将 $u$ 和 $fa_u$ 合并后就转化为了一个规模为 $n-1$ 的问题。实现时用 set 维护。

具体排序方式为临项交换，分讨一下两个点是当前顺序优还是交换后优即可。

这部分时间复杂度：$O(2^{m-n+1}n\log n)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 75;

int n, m;
int a[kMaxN], b[kMaxN], gs[kMaxN];
bool g[kMaxN][kMaxN];

namespace Sub1 {
int f[1 << 25];

void solve() {
  std::fill_n(f, 1 << n, 1e18);
  f[1] = 1;
  for (int s = 1; s < (1 << n); s += 2) {
    int gss = 0, sum = 0;
    for (int i = 1; i <= n; ++i)
      if (s >> (i - 1) & 1)
        gss |= gs[i], sum += b[i] - a[i];
    for (int i = 1; i <= n; ++i) {
      if ((gss >> (i - 1) & 1) && (~s >> (i - 1) & 1)) {
        int t = (s | (1 << (i - 1)));
        f[t] = std::min(f[t], std::max(f[s], a[i] - sum));
      }
    }
  }
  std::cout << f[(1 << n) - 1] << '\n';
}
} // namespace Sub1

namespace Sub2 {
struct Node {
  int a, b;
  friend bool operator <(Node n1, Node n2) {
    // return std::max(n1.a, n2.a - (n1.b - n1.a)) < std::max(n2.a, n1.a - (n2.b - n2.a));
    if ((n1.a < n1.b) != (n2.a < n2.b)) return n1.a < n1.b;
    if (n1.a < n1.b) return n1.a < n2.a;
    else return n1.b > n2.b;
  }
  friend Node operator +(Node n1, Node n2) {
    static Node ret;
    ret.a = std::max(n1.a, n1.a - n1.b + n2.a);
    ret.b = n1.b - n1.a + n2.b - n2.a + ret.a;
    return ret;
  }
} t[kMaxN];

int ans = 1e18, p[kMaxN], fa[kMaxN];

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void unionn(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) fa[fx] = fy;
}

void check() {
  std::set<std::pair<Node, int>> st;
  t[1] = {0, 0}, std::iota(fa + 1, fa + 1 + n, 1);
  for (int i = 2; i <= n; ++i)
    st.emplace(t[i] = {a[i], b[i]}, i);
  for (int c = 1; c <= n - 1; ++c) {
    int i = st.begin()->second, pp = find(p[i]); st.erase(st.begin());
    fa[i] = pp;
    if (pp != 1) st.erase({t[pp], pp});
    t[pp] = t[pp] + t[i];
    if (pp != 1) st.emplace(t[pp], pp);
  }
  // for (int i = 2; i <= n; ++i) std::cerr << p[i] << " \n"[i == n];
  ans = std::min(ans, t[1].a);
}

void dfs(int u) {
  if (u == n + 1) return check();
  for (int i = 1; i < u; ++i)
    if (g[i][u])
      p[u] = i, dfs(u + 1);
}

void solve() {
  dfs(2);
  std::cout << ans << '\n';
}
} // namespace Sub2

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 2; i <= n; ++i) {
    std::cin >> a[i] >> b[i];
  }
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::cin >> u >> v;
    g[u][v] = 1;
    if (n <= 25) gs[u] |= (1 << (v - 1));
  }
  if (n <= 25) Sub1::solve();
  else Sub2::solve();
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}