NOIp2018 宝藏

DP

每次新加入道路的话费与树的深度有关，所以记 $f(i,j,k)$ 为现在树的深度为 $i$ 全部点集为 $j$ 这一层的点集为 $k$，预处理出每种点集向另一种点集连边的最小花费，然而复杂度过大并不能过。思考一下，$k$ 是为了强制当前新加入的边连向上一次层。但是，如果新加入的边加入之前的层会更优就必然不会出现在这个状态里面，所以直接记 $f(i,j)$ 为现在树的深度为 $i$ 全部点集为 $j$ 的最小花费就行了。总复杂度为 $\mathcal O(3^n*n)$。

#include <iostream> 
#include <cstdio>
#include <cstring>
const int MAXN = 12;
const int INF = 0x3f3f3f3f;
int n, m;
int dis[MAXN | 1][MAXN | 1], dp[MAXN | 1][1 << MAXN], val[1 << MAXN][1 << MAXN], id[1 << MAXN];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
int main() {
  n = read();
  m = read();
  memset(dis, INF, sizeof(dis));
  for (int i = 1; i <= n; ++i) id[1 << (i - 1)] = i;
  for (int i = 1, u, v, w; i <= m; ++i) {
    u = read();
    v = read();
    w = read();
    dis[u][v] = dis[v][u] = std::min(dis[u][v], w);
  }
  memset(val, INF, sizeof(val));
  for (int j = 1; j < 1 << n; ++j) {
    for (int i = (j - 1) & j; i >= 1; i = (i - 1) & j) {
      val[i][j] = 0;
      int jj = j ^ i;
      while (jj > 0) {
        int now_lb = jj & -jj;
        now_lb = id[now_lb]; 
        int minn = INF;
        for (int k = 1; k <= n; ++k) {
          if ((i & (1 << (k - 1))) == (1 << (k - 1))) {
            minn = std::min(minn, dis[k][now_lb]);
          }
        }
        if (val[i][j] != INF && minn != INF) val[i][j] += minn;
        else val[i][j] = INF;
        jj -= jj & -jj;
      }
    }
  }
  memset(dp, INF, sizeof(dp));
  for (int i = 1; i <= n; ++i) {
    dp[1][1 << (i - 1)] = 0;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < 1 << n; ++j) {
      for (int j0 = (j - 1) & j; j0 >= 1; j0 = (j0 - 1) & j) {
        if (val[j0][j] != INF) dp[i][j] = std::min(dp[i][j], dp[i - 1][j0] + (i - 1) * val[j0][j]);
      }
    }
  }
  int ans = INF;
  for (int i = 1; i <= n; ++i) {
    ans = std::min(ans, dp[i][(1 << n) - 1]);
  }
  printf("%d\n", ans);
  return 0;
}