最小斯坦纳树算法介绍

介绍

• 现在有一个图，将它们作为全集$G=(V,E)$，我现在有一个这些点的子集$S$，$S$大概有十几个点，现在想从$G$中选出一个子图$G^{\prime }=(V^{\prime },E^{\prime })$，使得$S?V^{\prime }$，且$G^{\prime }$构成一个连通图的同时所有边的权值和最小

解法

• 首先显然结果是一棵树，因为如果有环的话就可以断开环使得答案变得更小
• 这种问题通常有一种思路，设$dp[i][S]$表示以$i$为根节点，节点集合为$S$的答案，$T$表示$S$的子集，那么应该有$$dp[i][S]=min(dp[i][S],dp[i][T]+dp[i][S?T])\stackrel{?}{1}$$
• 如果$i$的度数为$1$，那么有$$dp[i][S]=min(dp[i][S],dp[j][S]+w_{i,j})\stackrel{?}{2}$$
• 以上，递推扩展$S$到最大，即为答案
• $\stackrel{?}{1}$可以枚举子集得到，$\stackrel{?}{2}$是最短路的基本式，对于每个状态跑$dijkstra$即可
• 简单说一下枚举子集，就是把状态对应的二进制数减去1和自己做与运算，这样一直进行下去即可，数学表达式如下$$s=(s?1)\&s$$
• 设$S$的节点个数为$k$，总的节点数为$n$，枚举子集转移的时间复杂度为$O(n\times 3^k)$，$dijkstra$转移的时间复杂度为$O(nlogn\times 2^k)$，总的时间复杂度是$O(n\times 3^k+nlogn\times 2^k)$

例题

https://www.luogu.com.cn/problem/P6192

• 模板题，按照上面所述，转化为代码如下

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<int, int> > > g(n + 1);
  for(int i=0;i<m;i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  int st = (1 << k);
  vector<vector<int> > dp(n + 1, vector<int>(st, INF));
  vector<int> key(k);
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater< > > q;
  for(int i=0;i<k;i++) {
    cin >> key[i];
    dp[key[i]][1 << i] = 0;
  }
  function<void(int)> dijkstra = [&](int s) {
    vector<bool> vis(n + 1);
    while(!q.empty()) {
      auto u = q.top();
      q.pop();
      if(vis[u.second]) {
        continue;
      }
      vis[u.second] = true;
      for(auto v : g[u.second]) {
        if(dp[v.first][s] > dp[u.second][s] + v.second) {
          dp[v.first][s] = dp[u.second][s] + v.second;
          q.emplace(dp[v.first][s], v.first);
        }
      }
    }
  };
  for(int s=1;s<st;s++) {
    for(int i=1;i<=n;i++) {
      for(int sub=s;sub;sub=(sub-1)&s) {
        dp[i][s] = min(dp[i][s], dp[i][sub] + dp[i][s ^ sub]);
      }
      if(dp[i][s] != INF) {
        q.emplace(dp[i][s], i);
      }
      dijkstra(s);
    }
  }
  cout << dp[key[0]][st - 1];
  return 0;
}

https://www.luogu.com.cn/problem/P4294

• 这题主要是要把题目抽象出来，题目是说要使用最少的志愿者所有景点串起来，且景点数量最多十个，恰好满足最小斯坦纳树的情景，也就是把景点看做上面描述的$S$集合，要从$V$中选出点集$V^{\prime }$，使得$S?V^{\prime }$
• 我们把所有的点编号，设$dp[i][s]$表示根节点为$i$，所选景点集合为$S$的所需志愿者的最少数量，$a[i]$表示第$i$个景点所需的志愿者数量，按照最小斯坦纳树的想法，有下面的式子
  $$\{\begin{array}{rl}dp[i][S]& =min(dp[i][S],dp[i][S?T]+dp[i][T]?a[i]),degree[i]>1\stackrel{?}{1}\\ dp[i][S]& =min(dp[i][S],dp[j][S]+a[i]),degree[i]=1\stackrel{?}{2}\end{array}$$
• 其中$T$表示$S$的子集，因为$\stackrel{?}{1}$式中，两个集合合并的时候根节点重复计算了两遍，所以需要减去一个$a[i]$
• 但是还有一个问题，怎么求方案？这里其实和普通动态规划的方案求法是类似的，都是每一次转移的时候记录一下上一步的操作，根据每一步操作的某些数据信息，最后算出结果之后逆序倒推，具体看代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  int tot = n * m;
  vector<int> a(tot);
  int s = 0;
  int rt = -1;
  for(int i=0;i<tot;i++) {
    cin >> a[i];
    if(a[i] == 0) {
      rt = i;
      s += 1;
    }
  }
  int st = (1 << s);
  vector<vector<int> > dp(tot, vector<int>(st, INF));
  s = 0;
  for(int i=0;i<tot;i++) {
    if(a[i] == 0) {
      dp[i][1 << s] = 0;
      s += 1;
    }
  }
  // first记录最小值, second记录当前所在的点的位置
  priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<> > q;
  // first记录点信息, second记录所选点的状态
  vector<vector<pair<int, int> > > pre(tot, vector<pair<int, int>>(st));
  vector<vector<int> > flg(n, vector<int>(m));
  vector<int> xx = {1, 0, -1, 0};
  vector<int> yy = {0, 1, 0, -1};
  function<void(int, int)> Dfs = [&](int root, int state) {
    if(pre[root][state].second == 0) {
      return;
    }
    flg[root / m][root % m] = 1;
    // 与前面的状态转移正好是相反的
    if(pre[root][state].first == root) {
      Dfs(root, state ^ pre[root][state].second);
    }
    Dfs(pre[root][state].first, pre[root][state].second);
  };
  function<void(int)> dijkstra = [&](int state) {
    vector<bool> vis(tot);
    while(!q.empty()) {
      auto u = q.top();
      q.pop();
      int s1 = u.second.first * m + u.second.second;
      if(vis[s1]) {
        continue;
      }
      vis[s1] = true;
      for(int i=0;i<4;i++) {
        int dx = u.second.first + xx[i];
        int dy = u.second.second + yy[i];
        int s2 = dx * m + dy;
        if(dx >= 0 && dx < n && dy >= 0 && dy < m && dp[s2][state] > dp[s1][state] + a[s2]) {
          dp[s2][state] = dp[s1][state] + a[s2];
          // 记录前一个状态
          pre[s2][state] = make_pair(s1, state);
          q.emplace(dp[s2][state], make_pair(dx, dy));
        }
      }
    }
  };
  for(int k=1;k<st;k++) {
    for(int i=0;i<tot;i++) {
      for(int sub=k;sub;sub=(sub-1)&k) {
        int tmp = dp[i][sub] + dp[i][k ^ sub] - a[i];
        if(dp[i][k] > tmp) {
          dp[i][k] = tmp;
          // 记录前一个状态
          pre[i][k] = make_pair(i, sub);
        }
      }
      if(dp[i][k] != INF) {
        q.emplace(dp[i][k], make_pair(i / m, i % m));
      }
    }
    dijkstra(k);
  }
  // 特判没景点的情况
  if(rt == -1) {
    rt = 0;
    dp[rt][st - 1] = 0;
  }
  cout << dp[rt][st - 1] << '\n';

  Dfs(rt, st - 1);
  for(int i=0;i<n;i++) {
    for(int j=0;j<m;j++) {
      if(a[i * m + j] == 0) {
        cout << 'x';
      } else {
        cout << (flg[i][j] == 1 ? 'o' : '_');
      }
    }
    cout << '\n';
  }
  return 0;
}