学习笔记——斯坦纳树

斯坦纳树#

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

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

给定一个连通图 $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: \Desktop\P6192.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 < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * f;
}

int n, m, k, cnt, head[M], f[N][M], vis[N], key[N];
struct node{int u, v, w, next;}e[N << 1];
priority_queue, 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] <= f[u][s] + e[i].w) continue;//如果加入了这条边边权和更大了就不加
            f[v][s] = f[u][s] + e[i].w;//松弛
            q.push({f[v][s], v});//入堆
        }
    }
    return ;
}

signed main()
{
    memset(f, INF, sizeof f);
    n = read(), m = read(), k = read();
    for(int i = 1; i <= m; i ++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    for(int i = 1; i <= k; i ++)
    {
        key[i] = read();
        f[key[i]][1 << (i - 1)] = 0;//以关建点为根，只包含当前点的代价是0
    }
    for(int s = 1; s <= (1 << k); s ++)//枚举k个点的所有状态
    {
        for(int i = 1; i <= n; i ++)//枚举每一个点
        {
            for(int subs = s & (s - 1); subs; subs = s & (subs - 1))//枚举每一个子集
                f[i][s] = min(f[i][s], f[i][subs] + f[i][s ^ subs]);//DP取最小值
            if(f[i][s] != INF) q.push({f[i][s], i});//只要不是全是INF就可以试试
        }
        Dij(s);//跑DIJ
    }
    cout << f[key[1]][(1 << k) - 1] << endl;//输出以1为根的子树所有关键点都在里面最小的边权和
    return 0;
}

参考博客：https://www.luogu.com.cn/blog/ydz2010/si-tan-na-shu