题解 ABC326G【Unlock Achievement】

problem

有 \(n\) 项属性，第 \(j\) 个属性的等级 \(l_j\) 初始为 \(1\)，每提升一级花费 \(c_j\) 的钱。又有 \(m\) 项成就，第 \(i\) 项成就要求对于所有 \(1\leq j\leq n\)，都要 \(l_j\geq L_{i,j}\)，如果满足所有要求，获得 \(a_i\) 的钱。求你最多能获得多少钱。\(n,m\leq 50,L\leq 5\)。

solution

考虑网络流。不妨按照 2-sat 的方式思考，\(s_{j,p}\) 是一个 bool 变量，表示最终 \(l_j\geq p\) 的真假。\(t_i\) 表示最终成就 \(i\) 是否完成。为了统一行使，不妨先认为所有成就均已完成，你要升级或者放弃一部分成就，花费最少的钱满足限制。

最小割。使得所有点 \(p\) 都连边 \(S\to p\to T\)，规定割断左边的边表示这个点对应的命题成立，代价加在左边的边上，反之亦然。刻画限制：

• \(s_{j,1}\) 总是满足，满足的代价是 \(0\)。
• \(s_{j,p}(p>1)\) 满足的代价是 \(c_j\)，不满足的代价是 \(0\)。且如果 \(s_{j,p}\) 那么 \(s_{j,p-1}\)。\(\iff\) 若 \(s_{j,p}\)，那么 \(\neg s_{j,p-1}\) 的代价是无穷大。
• \(t_i\) 不满足的代价是 \(a_i\)。（一开始满足了所有成就）
• 如果 \(t_i\) 那么对所有 \(j\) 满足 \(s_{j,L_{i,j}}\)。\(\iff\) 如果 \(t_i\) 那么所有 \(\neg s_{j,L_{i,j}}\) 的代价是无穷大。
• （这里形如如果 \(a\) 那么 \(\neg b\) 的代价是无穷大 就是 从 \(b\) 连无穷大边到 \(a\)）

然后快乐最小割就行，点数 \(O(nL+m)\) 边数 \(O(nL+nm)\)，总是能过的。

code

#include "atcoder/maxflow"
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
typedef atcoder::mf_graph<int> graph;
int n, m, s0, t0, id[60][10], it[60], ans, tot = -1, c[60], a[60], L[60][60];
int main() { 
  scanf("%d%d", &n, &m);
  s0 = ++tot, t0 = ++tot;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    for (int j = 1; j <= 5; j++) id[i][j] = ++tot;
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &a[i]);
    ans += a[i];
    it[i] = ++tot;
  }
  graph g(tot + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 5; j++) g.add_edge(s0, id[i][j], j > 1 ? c[i] : 0);
    for (int j = 2; j <= 5; j++) g.add_edge(id[i][j - 1], id[i][j], 1e9);
  }
  for (int i = 1; i <= m; i++) {
    g.add_edge(it[i], t0, a[i]);
    for (int j = 1; j <= n; j++) {
      scanf("%d", &L[i][j]);
      g.add_edge(id[j][L[i][j]], it[i], 1e9);
    }
  }
  printf("%d\n", ans - g.flow(s0, t0));
  return 0;
}