斯坦纳树问题 题解

问题分析

我们需要连接所有相同频道的重要情报站，使得总花费最小。这是一个典型的**斯坦纳树（Steiner Tree）**问题：

给定一个图 $G=(V,E)$ 和边权 $w_i$ 给定终端节点集合 $T \subseteq V$（重要情报站） 求包含所有终端节点的最小权重子图

算法思路

1. 问题建模

将频道信息编码为状态压缩：$p \leq 10$，可以用 $2^p$ 种状态表示 $s[i]$：节点 $i$ 包含的频道集合（位掩码） $c[k]$：频道 $k$ 包含的所有重要情报站集合

2. 动态规划状态

定义 $f[mask][u]$：表示已连接频道集合为 $mask$，且当前树包含节点 $u$ 的最小花费。

3. 算法步骤

初始化

for (int i = 1; i <= n; ++i)
    f[s[i]][i] = 0;  // 单个节点的基础状态

状态转移

第一步：子集合并

for (int j = i; j; --j &= i)
    for (int k = 1; k <= n; ++k)
        f[i][k] = min(f[i][k], f[i ^ j][k] + f[j][k]);

这步通过子集划分合并不同频道集合：$f[mask][u] = \min\limits_{sub \subseteq mask} \{f[mask \oplus sub][u] + f[sub][u]\}$

第二步：Dijkstra 松弛

heap<pair<int, int>> hp;
for (int j = 1; j <= n; ++j)
    hp.emplace(f[i][j], j);

while (!hp.empty()) {
    auto [d, u] = hp.top(); hp.pop();
    if (f[i][u] != d) continue;
    
    for (auto [v, w] : e[u])
        if (d + w < f[i][v]) {
            f[i][v] = d + w;
            hp.emplace(d + w, v);
        }
}

在固定频道集合 $mask$ 下，用 Dijkstra 算法优化节点间距离。

最终整合

for (int i = 0; i < (1 << p); ++i) {
    int t = 0;
    for (int j = 0; j < p; ++j)
        if (i >> j & 1)
            t |= c[j + 1];  // 合并频道对应的节点集合
    g[t] = *min_element(f[t] + 1, f[t] + n + 1);
}

for (int i = 0; i < (1 << p); ++i)
    for (int j = i; j; --j &= i)
        g[i] = min(g[i], g[j] + g[i ^ j]);

将频道需求转化为节点集合需求，再用子集 DP 求最终解。

复杂度分析

状态数：$O(2^p \times n)$，其中 $p \leq 10$，$n \leq 1000$ 子集枚举：$O(3^p \times n)$ Dijkstra：$O(2^p \times (m + n \log n))$ 总复杂度：在数据范围内可行

样例解析

输入： $n=5, m=8, p=4$ 重要情报站：频道1包含节点1,2；频道2包含节点3,4

算法计算过程： 1.初始化各节点的频道集合 2.通过斯坦纳树算法找到连接所有频道的最小生成子图 3.最终找到最优解：连接节点1,2,3,4,5，总花费为4

输出：4

关键技巧

1.状态压缩：将频道需求编码为位掩码 2.子集DP：高效枚举所有频道组合 3.Dijkstra优化：在固定频道集合下求最短路径 4.斯坦纳树：经典算法解决终端节点连接问题

总结

本题通过斯坦纳树算法结合状态压缩动态规划，高效解决了多频道情报站连接问题。算法充分利用了 $p$ 较小的特点，通过位运算优化状态转移，在合理时间内求出最优解。