斯坦纳树学习笔记
abcdeffa
2020-03-14 20:40:04
## 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'$，我们采用下面的方式：
```cpp
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 部分的代码如下：
```cpp
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;
}
}
}
```
结合这两条转移式，我们就可以得出下面的代码了。
```cpp
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
```cpp
#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
```cpp
#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）