斯坦纳树学习笔记

Brief introduction

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

斯坦纳树问题即给出你一个有 n 个点 m 条边的有权无向图，然后选定 k 个点，让你求出使这 k 个点联通所需的最小代价，其实最小生成树是最小斯坦纳树的一种特殊情况。^{[2]}

在一秒内可以跑过的范围大概是 1 \leq k \leq 10，1 \leq n, m \leq 10^3，因为我们要状压，所以 k 一般来说不会很大。

Algorithm flow

首先我们首先可以发现一个结论：答案的子图 一定 是树，因为如果答案存在环，则删去环上任意一条边，则可以使代价变小。^{[3]}

解决这类问题，我们考虑设 f_{i, S} 表示以 i 为根，包含选定点的状态为 S 的情况下所需要的代价的最小值，其中当 S 在二进制下的第 i 位为 1 时表示包含了第 i 个关键点，为 0 则表示不包含。

那么我们可以得出我们的第一个转移式：

f_{i, S} = \min\{ f_{i, S'} + f_{i, S \oplus S'} \}

这条转移式就是将 S 拆分成 S' 和 (S \oplus S') 两个状态，这里的 (S \oplus S') 也可以写成 (S - S \land S')，一般来说习惯用 (S \oplus S')，这里的 S' 是 S 状态的一个子集。

对于枚举 S'，我们采用下面的方式：

for(int SS = (S - 1) & S;SS;SS = (SS - 1) & S)

这样就可以优化复杂度了。

我们已经解决了自己更新自己的问题了，那么我们怎么解决新加一条边的问题呢？

我们又可以想到下面的这条转移式：

f_{i, S} = \min(f_{j, S} + w)

其中 i 和 j 之间有一条边权为 w 的边，其中若 i 或 j 是关键点，则 S 就要包含它们。

这个怎么转移呢？

我们发现当 f_{j, S} 的值比当前的 f_{i, S} 的值优的话，那么就要满足 f_{j, S} + w < f_{i, S}，是不是像极了你做 SPFA 时的那个转移式？

于是我们考虑使用 SPFA 来做转移。

初始时 f_{i, S} 均为正无穷，f_{a_j, 2^{j - 1}} = 0，其中 a_j 是第 j 个选定点的编号。

第二条转移式具体怎用 SPFA 来转移？

我们先从小到大枚举 S，在对所有的 f_{i, S} 执行完第一条转移式 f_{i, S} = \min\{ f_{i, S'} + f_{i, S \oplus S'} \} 后，把所有满足 f_{i, S} 不为正无穷的 i 丢进队列里，然后跑 SPFA 更新就好啦。

SPFA 部分的代码如下：

void bfs (int S)
{
    while(tou != wei)
    {
        int x = dl[tou];
        for(int i = h[x];i;i = b[i].g)
        {
            int y = b[i].y;
            if(f[x][S] + b[i].c < f[y][S])
            {
                f[y][S] = f[x][S] + b[i].c;
                if(!vis[y])
                {
                    vis[y] = 1;
                    dl[wei] = y;
                    wei++;
                    if(wei >= maxN)
                    {
                        wei = 1;
                    }
                }
            }
        }
        vis[x] = 0;
        tou++;
        if(tou >= maxN)
        {
            tou = 1;
        }
    }
}

结合这两条转移式，我们就可以得出下面的代码了。

for(int S = 0;S <= ma; S++)
{
    tou = wei = 1;
    for(int SS = (S - 1) & S;SS;SS = (SS - 1) & S)
    {
        for(int i = 1;i <= n; i++)
        {
            f[i][S] = min(f[i][S], f[i][SS] + f[i][S ^ SS]);
        }
    }
    for(int i = 1;i <= n; i++)
    {
        if(f[i][S] < INF)
        {
            vis[i] = 1;
            dl[wei++] = i;
        }
    }
    bfs(S);
}

其中函数 bfs() 的内容已在上面给出。

最后的答案就是 \min_{i = 1}^p f_{i, 2^p - 1}，其中 p 是给定点的个数。

Example 1

题目来源：Luogu P6192 【模板】最小斯坦纳树

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

再给定包含 k 个结点的点集 S，选出 G 的子图 G'=(V', E')，使得 S\subseteq V'，G' 为连通图，且E' 中所有边的权值和最小。你只需要求出 E' 中所有边的权值和即可。

1 \leq n \leq 100, 1 \leq m \leq 500, 1 \leq k \leq 10

保证答案和输入的所有数均小于 2^{31}。

Solution 1

这道题目其实就是 斯坦纳树 的模板，直接用 斯坦纳树 来做就好了。

Code 1

#include <cstdio>
#include <cstring>
#define maxP 10
#define maxN 3010
const int INF = 707406378;
struct edge{ int x, y, c, g; } b[maxN << 1];
int len = 0, tou = 1, wei = 1;
int f[maxN][1 << maxP];
int color[maxP], num[maxP];
int vis[maxN], dl[maxN], h[maxN];
int min (int x, int y)
{
    return x < y ? x : y;
}
void ins (int x, int y, int c)
{
    len++;
    b[len].x = x;
    b[len].y = y;
    b[len].c = c;
    b[len].g = h[x];
    h[x] = len;
}
void bfs (int S)
{
    while(tou != wei)
    {
        int x = dl[tou];
        for(int i = h[x];i;i = b[i].g)
        {
            int y = b[i].y;
            if(f[x][S] + b[i].c < f[y][S])
            {
                f[y][S] = f[x][S] + b[i].c;
                if(!vis[y])
                {
                    vis[y] = 1;
                    dl[wei] = y;
                    wei++;
                    if(wei >= maxN)
                    {
                        wei = 1;
                    }
                }
            }
        }
        vis[x] = 0;
        tou++;
        if(tou >= maxN)
        {
            tou = 1;
        }
    }
}
int main ()
{
    int n = 0, m = 0, p = 0;
    scanf("%d %d %d", &n, &m, &p);
    for(int i = 1;i <= m; i++)
    {
        int x = 0, y = 0, c = 0;
        scanf("%d %d %d", &x, &y, &c);
        ins(x, y, c);
        ins(y, x, c);
    }
    memset(f, 127 / 3, sizeof(f));
    for(int i = 1;i <= p; i++)
    {
        scanf("%d", &num[i]);
        f[num[i]][1 << (i - 1)] = 0;
    }
    const int ma = (1 << p) - 1;
    for(int S = 0;S <= ma; S++)
    {
        tou = wei = 1;
        for(int SS = (S - 1) & S;SS;SS = (SS - 1) & S)
        {
            for(int i = 1;i <= n; i++)
            {
                f[i][S] = min(f[i][S], f[i][SS] + f[i][S ^ SS]);
            }
        }
        for(int i = 1;i <= n; i++)
        {
            if(f[i][S] < INF)
            {
                vis[i] = 1;
                dl[wei++] = i;
            }
        }
        bfs(S);
    }
    int ans = INF;
    for(int i = 1;i <= n; i++)
    {
        ans = min(ans, f[i][ma]);
    }
    printf("%d", ans);
    return 0;
}

Example 2

题目来源：Luogu P3264 [JLOI2015]管道连接

小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。该部门有 n 个情报站，用 1 到 n 的整数编号。给出 m 对情报站 u_i;v_i 和费用 w_i，表示情报站 u_i 和 v_i 之间可以花费 w_i 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 u_i 和 v_i 建立了通道，那么它们建立了通道连接；若 u_i 和 v_i 均与 t_i 建立了通道连接，那么 u_i 和 v_i 也建立了通道连接。

现在在所有的情报站中，有 p 个重要情报站，其中每个情报站有一个特定的频道。小铭铭面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。

现在请你求出最小的花费是多少。

Solution 2

如果我们设答案的状态 S 是由一颗或多棵斯坦纳树的状态 S_1、S_2、...、S_k，其中 1 \leq k \leq p，那么 S_i(1 \leq i \leq k) 必定满足如果它在二进制下的某一位是 1，那么这个状态肯定包含了所有和这个选定点的频道一样的点，那么我们对所有这样的状态求出它的斯坦纳树，然后状压 DP 一下就可以求出答案了。

状压 DP 的话就是设 g_S 表示当前让状态为 S 的选定点联通且 在满足题目要求的情况下 所需的最小代价，然后转移即可。

我卡了常，又多交了几遍才在洛谷上过了这题......

Code 2

#include <cstdio>
#include <cstring>
#define maxP 10
#define maxN 3010
#define min(x, y) ((x) < (y) ? (x) : (y))
const int INF = 707406378;
struct edge{ int x, y, c, g; } b[maxN << 1];
int len = 0, tou = 1, wei = 1;
int f[maxN][1 << maxP];
int vis[maxN], dl[maxN], h[maxN];
int abl[1 << maxP], g[1 << maxP];
int color[maxP], count[maxP], num[maxP], dy[maxP];
int read ()
{
    char c;
    int x = 0;
    c = getchar();
    while(c < '0' || c > '9')
    {
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}
void ins (int x, int y, int c)
{
    len++;
    b[len].x = x;
    b[len].y = y;
    b[len].c = c;
    b[len].g = h[x];
    h[x] = len;
}
void bfs (int S)
{
    while(tou != wei)
    {
        int x = dl[tou];
        for(register int i = h[x];i;i = b[i].g)
        {
            int y = b[i].y;
            if(f[x][S] + b[i].c < f[y][S])
            {
                f[y][S] = f[x][S] + b[i].c;
                if(!vis[y])
                {
                    vis[y] = 1;
                    dl[wei] = y;
                    wei++;
                    if(wei >= maxN)
                    {
                        wei = 1;
                    }
                }
            }
        }
        vis[x] = 0;
        tou++;
        if(tou >= maxN)
        {
            tou = 1;
        }
    }
}
int main ()
{
    int n = 0, m = 0, p = 0;
    n = read();
    m = read();
    p = read();
    for(register int i = 1;i <= m; i++)
    {
        int x = 0, y = 0, c = 0;
        x = read();
        y = read();
        c = read();
        ins(x, y, c);
        ins(y, x, c);
    }
    memset(f, 127 / 3, sizeof(f));
    memset(g, 127 / 3, sizeof(g));
    int cnt = 0;
    for(register int i = 1;i <= p; i++)
    {
        color[i] = read();
        num[i] = read();
        if(!dy[color[i]])
        {
            dy[color[i]] = ++cnt;
        }
        f[num[i]][1 << (i - 1)] = 0;
        count[dy[color[i]]] += (1 << (i - 1));
    }
    const int ma = (1 << p) - 1;
    for(register int S = 0;S <= ma; S++)
    {
        bool flag = true;
        for(register int i = 1;i <= cnt; i++)
        {
            int now = (S & count[i]);
            if(now && now != count[i])
            {
                flag = false;
                break;
            }
        }
        abl[S] = flag;
    }
    for(register int S = 0;S <= ma; S++)
    {
        tou = wei = 1;
        for(register int SS = (S - 1) & S;SS;SS = (SS - 1) & S)
        {
            for(register int i = 1;i <= n; i++)
            {
                f[i][S] = min(f[i][S], f[i][SS] + f[i][S ^ SS]);
            }
        }
        for(register int i = 1;i <= n; i++)
        {
            if(f[i][S] < INF)
            {
                vis[i] = 1;
                dl[wei++] = i;
            }
        }
        bfs(S);
        if(abl[S])
        {
            for(register int i = 1;i <= n; i++)
            {
                g[S] = min(g[S], f[i][S]);
            }
        }
    }
    for(register int S = 0;S <= ma; S++)
    {
        for(register int SS = (S - 1) & S;SS;SS = (SS - 1) & S)
        {
            g[S] = min(g[S], g[SS] + g[S ^ SS]);
        }
    }
    printf("%d", g[ma]);
    return 0;
}

Reference

[1] 百度百科-斯坦纳树（https://baike.baidu.com/item/%E6%96%AF%E5%9D%A6%E7%BA%B3%E6%A0%91/12796694?fr=aladdin）

[2] CocoT 的 CSDN 博客中的文章“斯坦纳树 Steiner Tree”（https://blog.csdn.net/wu_tongtong/article/details/78992913?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task）

[3] ix35_ 的洛谷博客中的文章“题解 P6192 【【模板】最小斯坦纳树】”（https://www.luogu.com.cn/blog/ix-35/solution-p6192）