题目分析

本题要求我们在一个连通的无向图中，选择一些边使得指定的 $p$ 个关键车站相互连通，并且总费用不超过最小可能费用的两倍。

解题思路

核心观察

1. 题目允许2倍近似解，这大大降低了难度
2. 关键点集 $S$ 相对较小（$p \times m \le 1.5 \times 10^7$）
3. 我们可以使用Steiner树的2-近似算法

算法步骤

步骤1：构建最短路径树

• 从任意一个关键点（代码中选择 pt[1]）出发，使用Dijkstra算法计算到所有点的最短距离
• 同时记录每个点的前驱节点 pre[v]，用于重建路径

步骤2：标记关键路径上的点

for (int i = 1; i <= p; ++i)
    for (int j = pt[i]; !vis[j]; j = pre[j])
        vis[j] = 1;

这段代码的作用是：

• 对于每个关键点，沿着最短路径回溯到起点
• 标记所有在关键点之间最短路径上的节点
• 这样确保了我们保留了连接关键点所需的所有中间节点

步骤3：在关键子图上求最小生成树

• 只在被标记的节点构成的子图上运行Kruskal算法
• 使用并查集来维护连通性
• 选择权重最小的边来连接所有关键点

代码详解

数据结构

struct Edge {
    int u, v, w;
    bool operator<(const Edge &e) const {
        return w < e.w;
    }
} e[M * 2];

存储所有边，并支持按权重排序。

Dijkstra算法

fill(dis + 1, dis + n + 1, 1e18);
pq.push({0, pt[1]}), dis[pt[1]] = 0;

从第一个关键点开始，计算单源最短路径。

关键路径标记

通过回溯前驱节点，标记所有在关键点连通路径上的节点。

Kruskal算法

sort(e + 1, e + etot + 1);
iota(fa + 1, fa + n + 1, 1);
for (int i = 1; i <= etot; ++i) {
    if (!vis[u] || !vis[v]) continue;  // 只考虑关键路径上的边
    if (find(u) != find(v))
        fa[find(u)] = find(v), res.push_back(i), ans += w;
}

为什么这是2-近似解

这个算法实际上是Steiner树问题的经典2-近似算法：

1. 首先构建关键点间的最短路径度量
2. 然后在这个度量空间上求最小生成树
3. 最后将MST中的边用原图中的实际路径替换

理论保证：解的费用 ≤ 2 × 最优Steiner树费用

时间复杂度

• Dijkstra：$O(m \log n)$
• 路径标记：$O(n)$
• 排序：$O(m \log m)$
• Kruskal：$O(m \alpha(n))$

总复杂度：$O(m \log n)$，在题目数据范围内可行。

样例分析

对于样例输入：

8 11
...（边信息）
4 2 5 7 8

算法：

1. 从关键点2开始Dijkstra
2. 标记连接关键点{2,5,7,8}的路径上的所有节点
3. 在标记的子图上求MST

输出：

42 5
2 3
3 5
5 6
6 7
6 8

总费用42，使用5条边，满足所有关键点连通。

总结

本题的关键在于利用题目给出的2倍近似条件，将NP难的Steiner树问题转化为可通过最短路径和最小生成树高效求解的问题。算法既保证了正确性，又具有较好的时间复杂度。