斯坦纳树学习笔记

斯坦纳树问题是组合优化问题¹ ，其中最常见的是最小斯坦纳树问题。

我们一般使用状压dp来求解最小斯坦纳树的问题，当然也有不用状压dp的题啦（

最小斯坦纳树

题意：

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

再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G^{\prime}=(V^{\prime},E^{\prime})$，使得：

$S\subseteq V^{\prime}$；

$G^{\prime}$ 为连通图；

$E^{\prime}$ 中所有边的权值和最小。

你只需要求出 $E^{\prime}$ 中所有边的权值和。

数据范围：

$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$。

保证给出的无向图连通，但可能存在重边和自环。

$\mathcal{Part\ 1}$

最小斯坦纳树问题，就是要花费最小的代价，连通给定的 $k$ 个关键点。

称答案为关键图，并称关键点构成的集合为关键集合。显然这个关键图是一棵树（最小斯坦纳树）。

考虑状压dp。设 $f_{i,S}$ 表示包含关键子集 $S$ 中所有点，且钦定 $i$ 为树根时的最小代价。

注意，这里的 $S$ 是关键子集，也就是我们并不关心非关键点选了哪些。

并且容易发现在关键图连出环的时候一定是不优的，因此我们不会算重答案。

但是为什么要钦定树根呢？因为不钦定根时的复杂度反倒会更高，因为不好快速转移。

$\mathcal{Part\ 2}$

考虑如何不重不漏地转移。（下文中使用 $a \downarrow b+c$ 表示 $a \gets \min\{a,~b+c\}$ ）

一棵以 $i$ 为根的树，有两种情况，第一种是 $i$ 的度数为 $1$ ，第二种是 $i$ 的度数大于 $1$ 。

对于 $i$ 的度数为 $1$ 的情况，我们可以枚举它在树上与 $i$ 相邻的点 $j~(j \in S)$ ，则

$f_{i,S} \downarrow f_{j,S} + w(j,i)$

对于 $i$ 的度数大于 $1$ 的情况，我们可以划分为若干个子树考虑，即（ $\subset$ 表示真包含）

$f_{i,S} \downarrow \min_{T \subset S}\left\{f_{i,T} + f_{i,S\setminus T}\right\}$

$\mathcal{Part\ 3}$

枚举顺序是斯坦纳树的最巧妙之处。

对于第二种转移，我们只要顺序枚举 $S$ ，然后枚举子集即可。

对于第一种转移，注意到只有 $f_{i,S} > f_{j,S} + w(j,i)$ 时才会更新 $f_{i,S}$ ，可以想到三角不等式。

因此对于每个 $S$ ，我们先枚举一遍 $T$ ，然后跑一遍 spfa 。

这里可以用 spfa 是因为它即使被卡，也不会成为复杂度瓶颈，并且一般情况下常数小于 Dijkstra。

注意，在这道题里不会成为复杂度瓶颈，是因为 $\mathcal{O}(nm)$ 较小，不代表所有此类题中均可用 spfa。

同时，在实现的时候，最好把状态交换一下，即记为 $\mathtt{f[S][i]}$ ，因为数组的连续访问会比较快。

时间复杂度 $\mathcal{O}(nm\times 2^k + n\times 3^k)$ ，但是平均复杂度比这个要低一些。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N 105
#define K 10
#define M 515

int n,m,k,pos=1,head[N],f[(1<<K)+5][N];
struct Edge{ int u,v,w,next; } e[M * 2];
void addEdge(int u,int v,int w)
{
    e[++pos] = {u,v,w,head[u]};
    head[u] = pos;
}
bitset<N> vis; queue<int> q;
void spfa(int S)
{
    int *d = f[S]; while(!q.empty()) q.pop();
    for(int i=0; i<n; i++) if(d[i] != INF){ q.push(i); vis[i] = 1; }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v, w = e[i].w;
            if(d[v] > d[u] + e[i].w)
            {
                d[v] = d[u] + e[i].w;
                if(!vis[v]) { q.push(v); vis[v] = 1; }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w; --u; --v;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0,x; i<k; i++)
    { cin >> x; --x; f[1 << i][x] = 0; }
    int mx = (1 << k) - 1;
    for(int S=1; S<=mx; S++)
    {
        for(int T = S&(S-1); T; T = (T - 1) & S)
            for(int i=0; i<n; i++) down(f[S][i], f[T][i] + f[S ^ T][i]);
        spfa(S);
    }
    int res = INF;
    for(int i=0; i<n; i++) down(res, f[mx][i]);
    cout << res << '\n';
    return 0;
}