啊啊啊爽到力，，，

过去太池沼力，没有做出来惹。现在看了看可能比较简单罢……

定义状态\(d_{i, S}\)表示当前已经被覆盖的点集为\(S\)，然后当前的生成树已经考虑到了第\(i\)层，转移看起来很毒……

所以预处理一个点集到另一个点集只走一步边来扩展，最优解是多少，然后转移就方便力……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int maxn = 12;
int G[15][15];
const int INF = 0x3f3f3f3f;
void add_edge(int u, int v, int d) {
  G[u][v] = std::min(G[u][v], d);
  G[v][u] = std::min(G[v][u], d);
}

int n;
int g1[(1 << maxn)][15], g2[(1 << maxn)][(1 << maxn)];
void process() {
  for(int s = 1; s < (1 << n); s ++) {
    for(int i = 1; i <= n; i ++) {
      g1[s][i] = INF;
      for(int j = 0; j < n; j ++) {
        if((1 << j) & s) {
          g1[s][i] = std::min(g1[s][i], G[j + 1][i]);
        }
      }
    }
  }
  for(int s = 1; s < (1 << n); s ++) {
    int k = (1 << n) - 1; k = k & (~s);
    for(int t = k; t > 0; t = (t - 1) & k) {
      g2[s][t] = 0;
      for(int i = 1; i <= n; i ++) {
        if((1 << (i - 1)) & t) {
          if(g1[s][i] == INF) {
            g2[s][t] = INF; break;
          }
          g2[s][t] += g1[s][i];
        }
      }
    }
  }
}

using ll = long long;
ll d[14][(1 << maxn)];
ll dp() {
  for(int s = 0; s < (1 << n); s ++) {
    d[1][s] = INF;
  }
  for(int i = 0; i < n; i ++) {
    d[1][(1 << i)] = 0;
  }
  for(int i = 2; i <= n; i ++) {
    for(int s = 1; s < (1 << n); s ++) {
      d[i][s] = INF;
      for(int t = (s - 1) & s; t != 0; t = (t - 1) & s) {
        d[i][s] = std::min(d[i][s], d[i - 1][t] + (ll(i - 1)) * g2[t][s ^ t]);
      }
    }
  }
  ll ans = INF;
  for(int i = 1; i <= n; i ++) {
    ans = std::min(ans, d[i][(1 << n) - 1]);
  }
  return ans;
}

int main() {
  memset(G, 0x3f, sizeof(G));
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w);
  }
  process(); printf("%lld\n", dp());
  return 0;
}

• 相关文章
• 全局相关文章