最小斯坦纳树算法介绍

2023-12-13 04:30:11

最小斯坦纳树

介绍

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

解法

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

例题

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 S S集合,要从 V V V中选出点集 V ′ V' V,使得 S ? V ′ S\subseteq V' S?V
  • 我们把所有的点编号,设 d p [ i ] [ s ] dp[i][s] dp[i][s]表示根节点为 i i i,所选景点集合为 S S S的所需志愿者的最少数量, a [ i ] a[i] a[i]表示第 i i i个景点所需的志愿者数量,按照最小斯坦纳树的想法,有下面的式子
    { d p [ i ] [ S ] = m i n ( d p [ i ] [ S ] , d p [ i ] [ S ? T ] + d p [ i ] [ T ] ? a [ i ] ) , d e g r e e [ i ] > 1 1 ? d p [ i ] [ S ] = m i n ( d p [ i ] [ S ] , d p [ j ] [ S ] + a [ i ] ) , d e g r e e [ i ] = 1 2 ? \left\{ \begin{aligned} dp[i][S]&=min(dp[i][S],dp[i][S-T]+dp[i][T]-a[i]),degree[i]>1\textcircled1\\ dp[i][S]&=min(dp[i][S],dp[j][S]+a[i]),degree[i]=1\textcircled2 \end{aligned} \right. {dp[i][S]dp[i][S]?=min(dp[i][S],dp[i][S?T]+dp[i][T]?a[i]),degree[i]>11?=min(dp[i][S],dp[j][S]+a[i]),degree[i]=12??
  • 其中 T T T表示 S S S的子集,因为 1 ? \textcircled1 1?式中,两个集合合并的时候根节点重复计算了两遍,所以需要减去一个 a [ i ] a[i] 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;
}

文章来源:https://blog.csdn.net/roadtohacker/article/details/134749450
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。