题解 P6192 【【模板】最小斯坦纳树】

xyf007 · 2021-10-15 23:56:43 · 题解

主要是来提供一种常数较小的写法，讲解部分略去
考虑最后的 DP 式子分为两部分：

大部分人就按照如上形式进行转移，但是这样常数很大，因为 数组访问不连续。在第一种转移的时候，内层枚举子集很不连续；在求最短路的时候，同样很不连续。

为了访问连续，一个想法就是交换数组两维。同时在第一种转移的时候，先枚举子集再枚举 i，这样数组访问就很连续了；在求最短路时，所有转移都在 f_{S} 中，比之前全部第二维为 S 快多了。
另一个优化是当 T<S\setminus T 的时候直接 break，因为这种情况及其子集已经在之前转移过了。这样可以让你的常数除以 2。
另外如果图比较稀疏，使用 SPFA 可以加快你的平均运行效率，即使出题人将其卡满成 O(nm) 依然不会成为复杂度瓶颈。

经过以上优化的代码可以通过 n=200,k=14 的数据，尽管理论复杂度达到了惊人的 9\times10^8。代码如下：

template <typename T>
void checkmax(T &x, T y) {
  if (x < y) x = y;
}
template <typename T>
void checkmin(T &x, T y) {
  if (x > y) x = y;
}
int n, m, k, dp[1024][101];
std::vector<std::pair<int, int>> g[101];
bool vis[101];
void Spfa(int S) {
  std::queue<int> q;
  for (int i = 0; i < n; i++)
    if (dp[S][i] != 0x3f3f3f3f) q.emplace(i), vis[i] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = false;
    for (auto &&[v, w] : g[u])
      if (dp[S][u] + w < dp[S][v]) {
        dp[S][v] = dp[S][u] + w;
        if (!vis[v]) q.emplace(v), vis[v] = true;
      }
  }
}
int main(int argc, char const *argv[]) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  std::cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    std::cin >> u >> v >> w, u--, v--;
    g[u].emplace_back(v, w), g[v].emplace_back(u, w);
  }
  std::memset(dp, 0x3f, sizeof(dp));
  for (int i = 0; i < k; i++) {
    int x;
    std::cin >> x, x--;
    dp[1 << i][x] = 0;
  }
  for (int S = 1; S < (1 << k); S++) {
    for (int T = S & (S - 1); T; T = (T - 1) & S) {
      if (T < (S ^ T)) break;
      for (int i = 0; i < n; i++) checkmin(dp[S][i], dp[T][i] + dp[T ^ S][i]);
    }
    Spfa(S);
  }
  std::cout << *std::min_element(dp[(1 << k) - 1], dp[(1 << k) - 1] + n);
  return 0;
}