首页 > 其他分享 >P6192 【模板】最小斯坦纳树 题解

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

时间:2024-08-30 10:14:15浏览次数:11  
标签:emplace leq int 题解 P6192 kMaxN 斯坦纳 集合 关键点

Description

给定一个包含 \(n\) 个结点和 \(m\) 条带权边的无向连通图 \(G=(V,E)\)。

再给定包含 \(k\) 个结点的点集 \(S\),选出 \(G\) 的子图 \(G'=(V',E')\),使得:

  1. \(S\subseteq V'\);

  2. \(G'\) 为连通图;

  3. \(E'\) 中所有边的权值和最小。

你只需要求出 \(E'\) 中所有边的权值和。

\(1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6\)。

Solution

求出的图一定是树,因为如果有环删掉环边一定更优。

假设已经求出了这个树,那么对于树上的每个点 \(u\),可以记录 \(S\) 表示 \(u\) 的子树出现的关键点集合。利用这个集合可以在图上模拟选树的儿子的过程。

设 \(f_{i,S}\) 表示图上与 \(i\) 连通的树包含 \(S\) 集合对应的关键点的最小边权和,可以得到两种转移:

  1. \(i\) 在树上的儿子有 \(\geq 2\) 个或者 \(i\) 为关键点,则儿子的集合一定小于 \(S\) 且互不相交,所以可以直接枚举儿子的集合然后求并就是答案。
  2. \(i\) 在树上只有一个儿子且 \(i\) 不为关键点,转移一定形如 \(f_{i,S}\leftarrow f_{j,S}+w\),跑 dijkstra 即可。

对于第一种转移实现上有一些细节,如果每次是先枚举 \(S\) 和 \(i\) 再枚举 \(i\) 的邻域的状态合并,这样单次就是 \(O(3^{|S|})\)。正确做法是直接让 \(f_{i,S}\leftarrow f_{i,S-T}+f_{i,T}\),因为 \(<S\) 的答案已经确定。这样做转移一的总时间复杂度就是 \(O(3^kn)\) 了。

容易发现这么 dp 不会出现不合法的情况,并且最优解一定会被算到。

时间复杂度:\(O(3^kn+2^km\log m)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 105, kMaxS = (1 << 10);

int n, m, k;
int f[kMaxN][kMaxS], id[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN];

void dijkstra(int s) {
  static bool vis[kMaxN];
  std::priority_queue<std::pair<int, int>> q;
  for (int i = 1; i <= n; ++i)
    q.emplace(-f[i][s], i), vis[i] = 0;
  for (; !q.empty();) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto [v, w] : G[u]) {
      if (f[v][s] > f[u][s] + w) {
        f[v][s] = f[u][s] + w;
        q.emplace(-f[v][s], v);
      }
    }
  }
}

void solve() {
  memset(f, 0x3f, sizeof(f));
  for (int i = 1; i <= n; ++i) f[i][id[i] ? (1 << (id[i] - 1)) : 0] = 0;
  for (int s = 0; s < (1 << k); ++s) {
    for (int i = 1; i <= n; ++i) {
      for (int t = s; t; t = (t - 1) & s)
        f[i][s] = std::min(f[i][s], f[i][s ^ t] + f[i][t]);
    }
    dijkstra(s);
  }
}

void dickdreamer() {
  std::cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    G[u].emplace_back(v, w), G[v].emplace_back(u, w);
  }
  for (int i = 1; i <= k; ++i) {
    int x;
    std::cin >> x;
    id[x] = i;
  }
  solve();
  int ans = 1e9;
  for (int i = 1; i <= n; ++i) ans = std::min(ans, f[i][(1 << k) - 1]);
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:emplace,leq,int,题解,P6192,kMaxN,斯坦纳,集合,关键点
From: https://www.cnblogs.com/Scarab/p/18388122

相关文章

  • BZOJ 4403序列统计题解
    缅怀zxc......
  • CSP-J 2021 初赛试题解析(第三部分:完善程序(2))
    完善程序二完整程序代码#include<iostream>usingnamespacestd;structpoint{intx,y,id;};boolequals(pointa,pointb){returna.x==b.x&&a.y==b.y;}boolcmp(pointa,pointb){returna.x!=b.x?a.x<b.x:a.y<b.y;}......
  • AT_arc170_b 的题解
    (一)因为\(a_i\)较小,那么可以对每一个\(i\),求出它右边离他最近的值为\(j\)的位置。枚举左端点和中间那个数\(a_j\),那么可以求出最小的\(k\)。这样就求出了每个左端点可以取到的最小的\(k\),记为\(b_i\)再从右到左\(b_i=\min(b_i,b_{i+1})\)。(二)AC代码。#include<bi......
  • AGC041D Problem Scores 题解
    在分值不降的条件下,要使任意一个大小为\(k\)的子集\(S\)内题目的分值之和少于任意一个大小为\(k+1\)的子集\(T\)内题目的分值之和,容易发现只需要取\(S\)为后\(k\)道题目,\(T\)为前\(k+1\)道题目时满足限制即可。换而言之,只需要对满足\(a\)的每一段长为\(k+......
  • P7075 [CSP-S2020] 儒略日 题解
    P7075[CSP-S2020]儒略日题面:题目描述为了简便计算,天文学家们使用儒略日(Julianday)来表达时间。所谓儒略日,其定义为从公元前4713年1月1日正午12点到此后某一时刻间所经过的天数,不满一天者用小数表达。若利用这一天文学历法,则每一个时刻都将被均匀的映射到数轴......
  • AT_ddcc2017_final_d なめらかな木 题解
    首先考虑暴力DP,设\(f(i,v_1,v_2,now)\)为已经将前\(i\)个数填入,\(i\)填在\(v_1\),\(j\)填在\(v_2\)点,已经填完点的状态是\(now\)(状压一下存在一个longlong里)的方案数。转移时直接枚举下一个点暴力转移,只需要保证新的点没有被访问过,并且填上新点后,\(v_1\)的所有邻接......
  • Luogu P4425 转盘 题解 [ 黑 ] [ 线段树 ] [ 贪心 ] [ 递归 ]
    转盘:蒟蒻的第一道黑,这题是贪心和线段树递归合并的综合题。贪心破环成链的trick自然不用多说。首先观察题目,很容易发现一个性质:只走一圈的方案一定最优。这个很容易证,因为再绕一圈回来标记前面的和等前面的标记完之后继续走是等价的,并且再绕一圈甚至可能更劣。于是,我们只用走......
  • 题解:P9938 [USACO21OPEN] Acowdemia II B
    前言:原来的tj干了一堆什么建图啊之类的,但其实不要这么复杂。注:下文中\(n\)是各成员名字列表。从\(K=1\)开整。如果情况是\(n_i<n_{i+1}<\cdots<n_j\),那么显然,咱就不知道关于成员\(n_i,\cdots,n_j\)的相对资历的信息。也许所有这帮成员都做出了相同的贡献。......
  • AWTF2024A Moving Slimes 题解
    发现史莱姆不合并也不会影响答案,所以就不用考虑合并了。这样处理之后,史莱姆的移动可以看作是受到与其不在同一位置的史莱姆的吸引所完成的,每只史莱姆可以给其他史莱姆一个单位的吸引力。因为每只史莱姆提供的吸引力是恒定的,所以考虑把吸引力放在它们的重心上,设\(pre_i\)表示坐......
  • 历年CSP-J初赛真题解析 | 2016年CSP-J初赛阅读程序(23-26)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客#include<iostream>usingnamespacestd;intmain(){intmax,min,sum,count=0;inttmp;cin>>tmp;......