本文已被洛谷日报收录。
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 则表示不包含。
那么我们可以得出我们的第一个转移式：
这条转移式就是将 $S$ 拆分成 $S’$ 和 $(S \oplus S’)$ 两个状态，这里的 $(S \oplus S’)$ 也可以写成 $(S - S \land S’)$，一般来说习惯用 $(S \oplus S’)$，这里的 $S’$ 是 $S$ 状态的一个子集。
对于枚举 $S’$，我们采用下面的方式：
1
| for(int SS = (S - 1) & S;SS;SS = (SS - 1) & S)
|
这样就可以优化复杂度了。
我们已经解决了自己更新自己的问题了，那么我们怎么解决新加一条边的问题呢？
我们又可以想到下面的这条转移式：
其中 $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 部分的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 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;
}
}
}
|
结合这两条转移式，我们就可以得出下面的代码了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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’$ 中所有边的权值和即可。
保证答案和输入的所有数均小于 $2^{31}$。
Solution 1
这道题目其实就是 斯坦纳树 的模板，直接用 斯坦纳树 来做就好了。
Code 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| #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] Coco_T_ 的 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）