斯坦纳树

斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。——– 百度百科

在图论里，一般用于解决形如：

给定一个连通图 (G)，给定 (k) 个关键点，选取一些边使得 (k) 个关键点连通，要求权值和最小。

最小生成树可以看作是一种特殊的斯坦纳树。

我们不难想到，给出的 (k) 个点可能并不能只用连接这 (k) 个点的边达到连通，有可能需要另外 (n-k) 个点的中转；其次，可能经过外面 (n-k) 个点中的点的中转，可以让边权和更小。

P6192 【模板】最小斯坦纳树

我们发现 (k) 很小，所以可以使用状压来试试。

我们用 (f[i][S]) 表示以 (i) 为根的树，包含 (S服务器托管网) 内所有点的最小边权值和。

首先我们知道最后形成的是一棵树，不难想到最后有个环的话去掉最大的那条边也可以。

我们考虑如何转移状态：

• (f[i][s] = min(f[i][s], f[i][s] + f[i][s text{^} subs]))

其中 (subs) 是 (s) 状态的一个子集，这个是保证一开始 (f[i][s]) 尽量小。

• 跑最短路，通过 (f[v][s] = f[u][s] + e[i].w) 来进行松弛，处理以所有点为根，子树包含 (s) 状态个关键点的最小边权和。

/*
 * @Author: Aisaka_Taiga
 * @Date: 2023-10-02 17:28:45
 * @LastEditTime: 2023-10-02 19:27:11
 * @LastEditors: Aisaka_Taiga
 * @FilePath: DesktopP6192.cpp
 * The heart is higher than the sky, and life is thinner than paper.
 */
#include 

#define pii pair
#define INF 0x3f3f3f3f
#define int long long
#define M 5010
#define N 510

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c  '9'){if(c == '-') f = -1; c = getchar();}
    while(c = '0') x = (x , greater > q;

inline void add(int u, int v, int w){e[++ cnt] = (node){u, v, w, head[u]}; head[u] = cnt;}

inline void Dij(int s)
{
    memset(vis, 0, sizeof vis);//清空vis
    while(!q.empty())
    {
        int u = q.top().second;//取出当前点
        q.pop();
        if(vis[u]) continue;//如果之前找过了就不用遍历了
        vis[u] = 1;//打标记
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;//终点
            if(f[v][s] 

参考博客：https://www.luogu.com.cn/blog/ydz2010/si-服务器托管网tan-na-shu

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net