题解 P7098 【[yLOI2020] 凉凉】

· · 题解

E

Algorithm 1

考虑枚举所有的情况，即每条线路经过哪一层，每条线路都有 n 种可能，爆搜即可，时间复杂度 O(n^n)。这里省略了与 m 有关的项。期望得分 35 分。

Algorithm 2

注意到数据范围明示状压 dp。考虑设计状态：f_{i, S} 表示考虑了放在深度为前 i 层的地铁，已经考虑了集合 S 中的所有路线的最小花费，转移显然：

f_{i, S} = \min_{s \subseteq S} f_{i - 1, s} + val(i, S - s)

其中 s 是 S 的子集，val(S - s) 表示 s 在 S 中的补集中的元素都放到第 i 层时的花费。val 是可以预处理的。具体可以参考 std和将来会有的民间题解。

暴力枚举 s 并判断 s 是不是 S 的子集来转移，共有 O(n 2^n) 个状态，单次转移复杂度 O(2^n)，总复杂度 O(n 4^n + m)，期望得分 70 分。

Algorithm 3

考虑优化算法二中的子集枚举方式。按照如下方式枚举子集显然可以精确枚举 S 的每个子集而不会无用枚举：

for (int s = S; s; s = (s - 1) & S)

这样转移的复杂度就变成了 O(2^k)，其中 k 表示 S 二进制为 1 的位数。考虑这样的时间复杂度为 O(m + n \times \sum\limits_{k = 0}^n C_{n}^k \times 2^k)。其中 C_{n}^k 表示二进制共有 k 位为 1 的数的个数。根据二项式定理，\sum\limits_{k = 0}^n C_{n}^k \times 2^k = \sum\limits_{k = 0}^n C_{n}^k \times 2^k \times 1^{n - k} = (2 + 1)^n = 3^n，因此总复杂度为 O(m + n \times 3^n)。期望得分 100 分。

值得注意的是，为了对标「NOIp2017 宝藏」的真实情况，本题没有加捆绑测试，也没有对着爆搜加剪枝卡（事实上数据量这么小根本就没法卡）。因此爆搜加剪枝可能可以获得比较可观的分数。

#include <cctype>
#include <cstdio>
#include <algorithm>

typedef long long int ll;

const int maxn = 15;
const int maxm = 100005;
const int maxt = 1 << maxn;
const ll INF = 1000000000000000000ll;

template <typename T>
inline void qr(T &x) {
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}

int n, m, upc;
int a[maxn][maxm], b[maxn][maxm], tmp[maxn];
ll fee[maxn][maxn], g[maxn][maxt], f[maxn][maxt];
bool ac[maxn][maxn];

int main() {
  qr(n); qr(m);
  upc = 1 << n;
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= m; ++j) {
      qr(a[i][j]);
    }
  }
  for (int i = 0; i < n; ++i) {
    qr(b[i][0]);
    for (int j = 1; j <= b[i][0]; ++j) {
      qr(b[i][j]);
    }
    std::sort(b[i] + 1, b[i] + 1 + b[i][0]);
    for (int j = 0; j < n; ++j) {
      for (int k = 1; k <= b[i][0]; ++k) {
        fee[i][j] += a[j][b[i][k]];
   //     printf("Aa%d %d %d %d %d %d\n", i, j, k, b[i][k], a[j][b[i][k]], fee[i][j]);
      }
  //    printf("ovO%d %d %d\n", i, j, fee[i][j]);
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      ac[i][j] = ac[j][i] = true;
      int u = 1, v = 1;
      while ((u <= b[i][0]) && (v <= b[j][0])) {
        if (b[i][u] == b[j][v]) {
          ac[j][i] = ac[i][j] = false; break;
        }
        if (b[i][u] < b[j][v]) ++u;
        else ++v;
      }
    }
  }
  for (int s = 1; s < upc; ++s) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (s & (1 << i)) {
      tmp[++cnt] = i;
      for (int j = 1; j < cnt; ++j) if (ac[tmp[j]][i] == false) {
        for (int k = 0; k < n; ++k) {
          g[k][s] = INF;
        }
        break;
      }
      if (g[0][s] == INF) break;
      for (int k = 0; k < n; ++k) {
        g[k][s] += fee[i][k];
      }
    }
  }
  for (int s = 1; s < upc; ++s) {
    f[0][s] = g[0][s];
  }
  for (int i = 1; i < n; ++i) {
    for (int s = 0; s < upc; ++s) {
      f[i][s] = f[i - 1][s];
      for (int t = s; t; t = (t - 1) & s) {
        f[i][s] = std::min(f[i][s], f[i - 1][s ^ t] + g[i][t]);
      }
     // printf("%d %d %lld\n", i, s, f[i][s]);
    }
  }
  printf("%lld\n", f[n - 1][upc - 1]);
}