引言
大家好，Codeforces的朋友们！几天前，我发现了一种有趣的方法来确定第二最小生成树的成本。
问题陈述
你被给定一个带权图，包含 $n$ 个顶点和 $m$ 条边。你需要构建两棵生成树：第一棵生成树必须是最小的，第二棵生成树也必须具有最小的边之和，但这两棵树至少有一条边是不同的（非正式地说：第一棵是最小生成树，第二棵尽可能接近最小生成树）。
预期解决方案
首先，我们对所有边按照成本进行排序，并使用克鲁斯克尔算法找到最小生成树。由于这两棵生成树必须至少有一条边不同，因此第二棵生成树必须不包含第一棵生成树的至少一条边。我们将遍历第一棵生成树的所有边，并假设每条边都不包含在第二棵生成树中（因此我们尝试排除 $n - 1$ 条边）。
接下来，我们只需标记该边为无用，并运行标准的克鲁斯克尔算法，跳过标记的边（我们甚至不需要重新排序边，因为它们的顺序不会改变）。由于这样，我们将找到没有特定边的最小生成树。这些生成树中最便宜的将是第二棵最小生成树。
最佳解决方案
在开始解决方案之前，需要阐明一个重要的引理。
更大的最小生成树引理
存在一棵第二最小生成树，它与最小生成树的不同之处仅在于一条边。
证明
设 $T_1, T_2, T_3, ... T_k$ 是生成树，使得：$T_i$ 与 $T_{i + 1}$ 通过移除边 $r_i$ 和添加边 $a_i$ 不同。
我们可以通过查找不在最小生成树中的每条边来构造第二棵最小生成树。如果我们将这条边添加到树中，它将与路径之间形成一个循环，因此我们必须丢弃路径上任何边。我们需要移除路径上最昂贵的边（例如，可以使用二进制提升找到：只需预计算每个跳跃的最大边权并在路径的两半中找到它）。
算法步骤
- 找到最小生成树（MST）。
- 预计算二进制提升以获得树上的最大边。
- 找到以最小方式增加答案的边（$\nabla_{ans} = e_{new} - e_{old}$）。
时间复杂度
$O(m \log n) + O(n \log n) + O((m - n) \log n) = O(m \log n)$。
额外内容
特定图中的最小生成树数量
你被给定一个带权图，包含 $n$ 个顶点和 $m$ 条边，其中每个权重出现的次数不超过三次。你需要找到该图中最小生成树的数量，结果取模 $10^9+7$。
解决方案
由于更大的最小生成树引理的证明，我们可以理解每棵最小生成树具有相同数量的某一权重的边。我们可以对每个权重进行独立分析，寻找可能的变化组合。
最后一步是，找到创建最小生成树的所有变体，只需将每个权重的变体数相乘即可。
时间复杂度
$O(m \log n)$。
感谢你的阅读！希望你喜欢这篇文章！
博主点评： 本文详细解读了第二最小生成树的构造过程，通过引理和算法的结合，展示了复杂问题的简洁解决方案。这种思路对优化算法设计具有重要的启发意义，值得深入研究和实践。