题目理解

有一张无向图，共有 n 个点，每个点有一个权值 aᵢ。

图中已经有 m 条边，我们要通过加边把它变成连通图。

每次加边的代价是：这条边连接的两个连通块合并后，新的连通块中最大的节点权值。

问：连通整个图的最小总代价是多少？

思路分析

假设我们一开始有 k 个连通块。

每个连通块都有一个“代表值”，就是这个连通块中最大的节点权值（因为合并后的连通块最大权值会保留下来，成为下次合并的代价）。

关键规律：

• 每次合并两个连通块 A 和 B，代价是 max(最大权值(A), 最大权值(B))。
• 为了让总代价最小，我们应该每次用最小的权值连通块去合并其他块吗？ 不一定。 实际上，有一个更简单的思路： 假设所有连通块的最大权值从小到大排序为 v₁, v₂, …, vₖ。 如果每次合并都让当前全局最小权值的连通块去参与合并，那么每次合并的代价就是另一个连通块的最大权值（因为另一个通常更大）。 为了最小化总代价，我们应该用最小权值的连通块去合并其他所有连通块，这样除了最小权值的连通块外，其他每个连通块的权值都会在合并时被计入一次代价。

算法步骤

1. 用并查集处理已有的 m 条边，得到初始的连通块。
2. 对每个连通块，记录其“块内最大权值”。
3. 设一共有 k 个连通块，它们的最大权值分别为 w₁, w₂, …, wₖ。
4. 找出其中最小的权值 min_w。
5. 总最小代价 = 所有 wᵢ 的总和 − min_w + min_w × (k−1) 吗？ 不，更简单的计算是： 总代价 = (所有连通块最大权值之和) − min_w，然后加上 (k−2) × min_w？ 等一下，我们推理一下。

正确计算方法

假设有 k 个连通块，权值（块内最大权值）为 w₁, w₂, …, wₖ，且 w₁ 是最小的。

最优合并顺序是：

• 第一步：合并 w₁ 和 w₂，代价是 max(w₁, w₂) = w₂。
• 新连通块的权值是 max(w₁, w₂) = w₂。
• 第二步：合并这个新块（权值 w₂）和 w₃，代价是 max(w₂, w₃) = w₃。
• ...
• 第 k−1 步：合并权值 wₖ₋₁ 的新块和 wₖ，代价是 max(wₖ₋₁, wₖ) = wₖ。

总代价 = w₂ + w₃ + ... + wₖ = (w₁ + w₂ + ... + wₖ) − w₁。

所以：

最小总代价 = 所有连通块的最大权值之和 − 最小的那个连通块最大权值。

代码解释

import sys
input = sys.stdin.readline
min_n = lambda a,b: b if a>b else a

n, m = map(int, input().split())
nums = list(map(int, input().split()))  # 节点权值
union = list(range(n))

def find(u):
    root = u
    while root != union[root]:
        root = union[root]
    while u != root:
        p = union[u]
        union[u] = root
        u = p
    return root

def join(u, v):
    u_p, v_p = find(u), find(v)
    if u_p == v_p: return
    # 让权值小的根指向权值大的根，这样根节点权值就是块内最大权值
    if nums[u_p] > nums[v_p]:
        u_p, v_p = v_p, u_p
    union[u_p] = v_p

# 合并已有的边
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    join(u, v)

# 统计每个连通块的最大权值（即根节点的权值）
total = 0
mini = nums[find(0)]
for i in range(n):
    if i == find(i):  # 是根节点，代表一个连通块
        total += nums[i]
        mini = min_n(mini, nums[i])

print(total - mini)

复杂度

• 并查集操作近似 O(α(n))，α 是反阿克曼函数，接近常数。
• 总复杂度 O((n+m)α(n))，