斯坦纳树学习笔记

2020-07-02

SPFA 信息学斯坦纳树最短网络

Brief introduction

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

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

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

Algorithm flow

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

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

f_{i, S} = min{ f_{i, S’} + f_i,S⊕S′}

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

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

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

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="cpp" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">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⊕S′} 后，把所有满足 f_i,S 不为正无穷的 i 丢进队列里，然后跑 SPFA 更新就好啦。

SPFA 部分的代码如下：

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="generic" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">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;
        }
    }
}

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

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="generic" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">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()bfs() 的内容已在上面给出。

最后的答案就是![](https://www.zicode.com/wp-content/uploads/2020/07/image.png) ，其中 p 是给定点的个数。## Example 1

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

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

再给定包含 k 个结点的点集 S ，选出 G 的子图 G′=(V′,E′) ，使得 S⊆V′ ， G′ 为连通图，且 E′ 中所有边的权值和最小。你只需要求出 E′ 中所有边的权值和即可。1≤n≤100,1≤m≤500,1≤k≤10

保证答案和输入的所有数均小于 2³¹ 。

Solution 1

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

Code 1

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="cpp" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">#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 也建立了通道连接。

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

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

Solution 2

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

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

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

Code 2

<pre class="EnlighterJSRAW" data-enlighter-group="" data-enlighter-highlight="" data-enlighter-language="cpp" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-theme="" data-enlighter-title="">#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）

阅读

Rust的错误处理机制

Go程序员的Rust之旅（待续）

Go自定义时间字段的json格式

Go语言如何识别图片的主要色值

go mod使用pseudo-version如何确认版本号？

WSL2磁盘读写性能优化

Windows下部署和使用Kubernetes

WinUI学习之Cultures in Action项目

winui3问题：点击事件不生效

挑战树莓派：RISC-V 微型计算机 PicoRio 发布

go语言实现syslog_collector (1篇文章) Rust编程 (7篇文章) Zola教程 (5篇文章) zola实践 (1篇文章)

rust (7) zola (6) go (5) 树莓派 (3) python (3) zinotes (2) 游戏 (2) 信息学 (2) wsl (2) winui (2) ubuntu (2) 算法 (2) 最短网络 (1) ziblogs (1) xaml (1) wordpress (1) windows (1) vscode (1) 图数据库 (1) 图计算 (1)