首页 > 其他分享 >最小斯坦纳树

最小斯坦纳树

时间:2024-02-01 09:58:27浏览次数:25  
标签:vis item int tree 最小 斯坦纳 second dp

最小斯坦纳树

给定 \(k\) 个关键点必须选,选一些点,选一些边连接他们,求总边权最小。

首先最终肯定选出一棵树。看到 \(k\) 的范围,果断状压。

\(dp[i][S]\) 表示以 \(i\) 为根,至少(不是恰好)包含 \(S\) 中的关键点的最小边权总和。

如果最终的树中 \(i\) 的度数 \(>1\),考虑把树分成两个树,各自包含不同的关键点:

\(dp[i][S]\leftarrow \min(dp[i][S],dp[i][T]+dp[i][S-T]).\)

\(T\) 是枚举的 \(S\) 的一个真子集。

否则,就考虑 \(i\) 唯一连着的结点 \(j\):

\(dp[i][S]\leftarrow \min(dp[i][S],dp[j][S]+w(j,i)).\)

我们发现,这个式子和求最短路的松弛式子意外的相似:

\(dist(v)\leftarrow \min(dist(v),dist(u)+w(v,u)).\)

我们可以通过求最短路的方式求。我们可以在每次从队列中取出 \(i\) 这个结点,然后拓展 \(i\) 的所有邻点。

详见代码注释。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
int n, m, k;

struct edge {
  int to, next, w;
} e[maxn << 1];

int head[maxn << 1], tree[maxn << 1], tot;
int dp[maxn][5000], vis[maxn];
int key[maxn];
priority_queue<P, vector<P>, greater<P> > q;

void add(int u, int v, int w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void dijkstra(int s) {  
// 求解最短路,注意这里的S是给定的状态,dijkstra应当只更新dp[x][s],真正的起点已经在调用之前塞进队列里了 
  memset(vis, 0, sizeof(vis));
  while (!q.empty()) {
    P item = q.top();
    q.pop();
    if (vis[item.second]) continue;
    vis[item.second] = 1;
    for (int i = head[item.second]; i; i = e[i].next) {
      if (dp[tree[i]][s] > dp[item.second][s] + e[i].w) { 
	  //如果tree[i]这个点当作根只有item.second(通过i拓展了若干次的结点得到item.second) 这一个儿子,
	  //那么根据状态转移式,可以用dp[item.second][s]尝试更新dp[tree[i]][s]
	  //注意这里即使使用了s之外的关键点为根也无所谓——我们定义的dp是至少不是恰好 
        dp[tree[i]][s] = dp[item.second][s] + e[i].w;
        q.push(P(dp[tree[i]][s], tree[i]));
      }
    }
  }
}

int main() {
  memset(dp, INF, sizeof(dp));
  scanf("%d %d %d", &n, &m, &k);
  int u, v, w;
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d", &u, &v, &w);
    add(u, v, w);
    tree[tot] = v;
    add(v, u, w);
    tree[tot] = u;
  }
  for (int i = 1; i <= k; i++) {
    scanf("%d", &key[i]);
    dp[key[i]][1 << (i - 1)] = 0; //dp初值 
  }
  for (int s = 1; s < (1 << k); s++) {
    for (int i = 1; i <= n; i++) {
      for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) { //子集枚举,复杂度 O(3^n) 
        dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]); //第一个转移式子 
    	}
      if (dp[i][s] != INF) q.push(P(dp[i][s], i)); //如果连起点都到达不了就不必要了(注意这里提前放好起点) 
    }
    dijkstra(s); //拓展,dp[i][S]能尝试更新所有 dp[x][S],x是任意i可达的结点 
  }
  printf("%d\n", dp[key[1]][(1 << k) - 1]); //其实这里根取哪个关键点都无所谓 
  return 0;
}

标签:vis,item,int,tree,最小,斯坦纳,second,dp
From: https://www.cnblogs.com/FLY-lai/p/18000602

相关文章

  • 【算法】斯坦纳树
    参考资料OI-Wiki:斯坦纳树T_a_r_j_a_n:[图论]-------斯坦纳树编程客:集合枚举子集-学习笔记概念斯坦纳树原本是在一个几何图中提出来的问题。在一个平面内给出\(n\)个点\(p_i\),可以加入一些新的点(称为斯坦纳点),要求在使得这些点连通并且边的总长度最小。在OI中,斯坦......
  • P1029 最大公约数和最小公倍数问题
    321上题目链接:P1029[NOIP2001普及组]最大公约数和最小公倍数问题本小蒟蒻的原始思路就是枚举所有范围内的数,分别求出他们的最大公约数和最小公倍数,再看是否满足题意。于是就有了以下一言难尽的东西(;′⌒`)↓#include<stdio.h>intmain(){intx,y,count;sc......
  • SysTrayIcon 改的 python tkinter 最小化至系统托盘,适用TTK
    网上的SysTrayIcon改的,Tk页面最小化至托盘,托盘图标左键单击恢复Tk界面1.点击最小化隐藏至托盘2.托盘图标右键菜单展示,左键返回Tk界面。托盘图标可以自定义,修改了SysTrayIcon更容易调用,Demo窗口加了注释,具体查看_Main类。代码如下:importwin32api,win32con,win32gui_str......
  • 最小生成树
    最小生成树概念给定一个无向图,在图中选择若干条边把图的所有的节点连接起来,要求边长之和最小。在图论中叫做最小生成树。Prim算法Prim算法生成最小生成树的过程基于贪心思想,每次将距离已经连通部分最近的点和对应的边加入连通部分,使得连通部分逐渐扩大,最后将整个图连接起来并......
  • 1,2,3……n的所有数的最小公倍数?
    importmathdeflcm(a,b):returna*b//math.gcd(a,b)deflcm_range(n):lcm_value=1foriinrange(2,n+1):lcm_value=lcm(lcm_value,i)returnlcm_valuen=81#输入给定的数值nresult=lcm_range(n)......
  • 最小表示法&Manacher学习笔记+杂题
    字符串系列前言:孩子从小就自卑。四、最小表示法&Manacher学习笔记+杂题相关题单:戳我1.最小表示法最小表示法是用于解决字符串最小表示问题的方法。(1)字符串的最小表示:字符串\(s\)的最小表示为与\(s\)循环同构的所有字符串中字典序最小的字符串。循环同构指的是当字符......
  • 最小表示法&Manacher学习笔记+杂题
    字符串系列前言:孩子从小就自卑。四、最小表示法&Manacher学习笔记+杂题相关题单:戳我1.最小表示法最小表示法是用于解决字符串最小表示问题的方法。(1)字符串的最小表示:字符串\(s\)的最小表示为与\(s\)循环同构的所有字符串中字典序最小的字符串。循环同构指的是当字符......
  • [office] MAX、MIN与IF结合,统计众多部门中同一部门数据最大值与最小值
    一位做电商数据分析的朋友说,他要对所管理的六个仓库的销售额进行对比统计,统计出每个仓库的最高与最低销售额。他有几万行的数据,简化到下面几行,以方便清楚统计公式。公式实现在E2单元格输入公式:“=MAX(IF($A$2:$A$16=D2,$B$2:$B$16))”,按“Ctrl+Shift+Enter”结束,向下填充,即可计算出......
  • 极速搭建基于mvc5的最小框架
    前言开发环境vs2019创建项目项目文件结构新建控制器新建视图编写视图代码编写控制器代码修改默认路由运行测试查看结果......
  • 【板子】字符串最小表示法
    //lgp1368//Copyrightyeyou26#include<bits/stdc++.h>usingnamespacestd;longlonga[600005];intn;voidinit();voidsolve(){inti=1,j=2,k=0;while(i<=n&&j<=n){k=0;while(a[i+k]==a[j+k]&&am......