斯坦纳树学习笔记

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

我们一般使用状压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;
}