acwing-388. 四叶草魔杖

发表于 分类于 阅读次数： Waline： 本文字数： 857 阅读时长 ≈ 3 分钟

考点

  • 最小生成树
  • 状态压缩DP

题解

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
const int maxn = 16, maxm = (1 << 16), inf = 0x3f3f3f3f;
int n, m, a[maxn], s[maxm], d[maxm], fa[maxn], dp[maxm];

struct node {
  int x_, y_, z_;
  bool operator<(const node &x) const { return z_ < x.z_; }
} e[maxm];

int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

int kruskal(int state) {
  for (int i = 0; i < n; ++i) {
    if ((1 << i) & state) fa[i] = i;
  }
  int ans = 0;
  for (int x, y, i = 1; i <= m; ++i) {
    if (((1 << e[i].x_) & state) && ((1 << e[i].y_) & state)) {
      x = find(e[i].x_), y = find(e[i].y_);
      if (x != y) {
        ans += e[i].z_;
        fa[x] = y;
      }
    }
  }
  // 最终所有人的祖先应该是一样的
  int ancestor = -1;
  for (int i = 0; i < n; ++i) {
    if ((1 << i) & state) {
      if (ancestor == -1) {
        ancestor = find(i);
      } else if (ancestor != find(i)) {
        return inf;
      }
    }
  }
  return ans;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int x, y, z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    e[i].x_ = x, e[i].y_ = y, e[i].z_ = z;
  }
  // 状态压缩，每一位代表每个点选还是不选，0不选1选
  // 每个状态由若干个连通块组成
  for (int i = 0; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j) {
      if ((1 << j) & i) s[i] += a[j];
    }
  }
  // 对所有连通块求最小生成树
  // 每个大的连通块，当然有可能拆分成若干个内部的小连通块，它们的开销和可能更小
  // 但小连通块们及其组合的情况一定会被先算出来，
  // 所以每次只需要把当前的大连通块当做整体看就行
  memset(d, 0x3f, sizeof(d));
  sort(e + 1, e + 1 + m);
  for (int i = 0; i < (1 << n); ++i) {
    if (s[i]) continue;
    d[i] = kruskal(i);
  }
  // 一个点都没有当然没开销
  memcpy(dp, d, sizeof(d));
  dp[0] = 0;
  for (int i = 1; i < (1 << n); ++i) {
    if (s[i]) continue;
    for (int k, j = i; j; j = (j - 1) & i) {
      k = i ^ j;
      if ((j & k) || s[j] || s[k]) continue;
      dp[i] = min(dp[i], dp[j] + dp[k]);
    }
  }
  if (dp[(1 << n) - 1] == inf)
    puts("Impossible");
  else
    cout << dp[(1 << n) - 1] << endl;
  return 0;
}

思路

根据题意，最终目的是要让所有宝石的能量值归零。

很容易想到以下步骤：

  1. 先找出所有总和等于0的选取情况。

    因为最多只有16个宝石，可以使用状态压缩进行保存，0表示不取1表示取。

    每个状态的总和保存在s[state]，比如s[0110]代表选取第2、第3个宝石的情况。

  2. 对上述每一种合法的选取状态求最小生成树。

    当然，某些时候该状态并不是连通的，此时最小生成树返回inf即可。

    每个状态的最小生成树保存至d[state]

  3. 设dp[state]代表state选取情况下，让所选宝石的能量值都归0的最小开销。

    初始状态dp[state]就等于d[state]，且dp[0]=0，没选任何宝石肯定没有任何开销。

    那么dp[i] = min(dp[i], dp[j] + dp[k])，其中j和k互斥，且j | k等于i，相当于遍历i的所有子集组成。

    互斥是因为选取方案不可能有相交，同一个点怎么可能出现两次呢？

    最终答案就等于dp[(1 << n) - 1]

dp正常都有两种写法，本题的另一种写法就是：

1
2
3
4
for (int i = 0; i < (1 << n); i++)
  if (!s[i])
    for (int j = 0; j < (1 << n); j++)
      if (!(i & j) && !s[j] && !s[i | j]) dp[i | j] = min(dp[i | j], dp[i] + dp[j]);

但显然这样会超时，高达1亿的时间复杂度