题解 | #小红的图上加边#

一、 问题分析

1. 问题抽象

本问题的本质是在一个给定的森林（由多个连通分量组成的无向图）中添加边，使得所有节点最终处于同一个连通分量内。

• 节点与边：节点数为 ，已有边数为 。
• 初始状态：给定边已经将图划分为 个连通分量。
• 操作代价：每添加一条连接两个不同连通分量 和 的边，代价为 。即合并后的新连通分量中的最大权值。
• 优化目标：最小化将 个连通分量合并为一个连通分量的总代价。

2. 核心属性

• 合并次数：若初始有 个连通分量，合并为 1 个连通分量固定需要进行 次加边操作。
• 代价单调性：任意连通分量的最大权值在合并过程中是单调不减的。
• 贪心抉择：为了让总代价最小，在每次合并时，我们应尽可能选取结果中“新最大值”最小的合并方案。

二、 算法：贪心策略

1. 策略推导

假设我们现在有 个连通分量，其各自内部的最大权值集合为 。 我们将这些最大值按升序排列，即 。

如果我们进行一次合并操作：

• 方案 A：合并 所在的块和 所在的块。
  • 代价为 。
  • 合并后的新块的最大值为 。
  • 此时剩余块的最大值集合变为 。
• 方案 B：合并 所在的块和 所在的块。
  • 代价为 。
  • 合并后的新块的最大值为 。
  • 此时剩余块的最大值集合变为 （其中 被移除了）。

结论：在每一轮合并中，最好的策略是将当前具有最小最大值的块与其他块合并。为了让后续代价也尽可能小，我们始终保持一个“核心块”，并将其他块依次合并进去。

2. 最小代价公式

最优的操作顺序是将 依次与 进行合并。

1. 合并 ：代价 ，新块最大值 。
2. 合并 (新块, )：代价 ，新块最大值 。 ... . 合并 (新块, )：代价 ，新块最大值 。

总最小代价为：。 即：除了所有连通分量中“最大权值最小”的那一个以外，其余所有连通分量的最大权值之和。

三、 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    vector<int> parent;
    vector<int> maxv;
    int n;

    DSU(int n, const vector<ll>& a): n(n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        maxv.assign(n + 1, 0);
        copy(a.begin(), a.end(), maxv.begin() + 1);
    }

    int find(int x) {
        return (parent[x] == x) ? parent[x] : (parent[x] = find(parent[x]));
    }

    void unite(int u, int v) {
        int ru = find(u);
        int rv = find(v);
        if (ru != rv) {
            parent[rv] = ru;
            maxv[ru] = max(maxv[ru], maxv[rv]);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    DSU dsu(n, a);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    vector<int> max_values;
    for (int i = 1; i <= n; i++) {
        if (dsu.parent[i] == i) {
            max_values.push_back(dsu.maxv[i]);
        }
    }

    int k = max_values.size();
    sort(max_values.begin(), max_values.end());
    ll ans = 0;
    for (int i = 1; i < k; i++) {
        ans += max_values[i];
    }

    cout << ans << endl;
}

四、 复杂度分析

1. 时间复杂度

• 识别连通分量：使用 DSU 或邻接表 DFS，复杂度为 或 。
• 寻找分量最大值：线性扫描所有节点，复杂度 。
• 排序：对最多 个分量的最大值进行排序，复杂度 。
• 总体复杂度：。

2. 空间复杂度

• 图存储/并查集：。
• 分量最大值存储：。
• 总体复杂度：。