B 小沙的魔法

原题链接

思路

• 首先，将问题转化为：将高度为$h_{i}h\_i$的城市降为0
• 如果不进行合并操作，需要进行$ans={\sum }_{i=1}^n{h}_{i}ans=\backslash sum\; \_\{i=1\}\; ^\; \{n\}h\_i$次操作2
• 对每条边$a-b(a\mathrm{和}b\mathrm{为}\mathrm{城}\mathrm{市}\mathrm{编}\mathrm{号})a-b(a和b为城市编号)$, 如果将$a\mathrm{和}ba和b$连接, 那么操作次数就会减少$min(h[a],h[b])min(h[a],h[b])$，比如高10和高5的城市相连，原本需要15次操作，连接后节约了min(10,5)次，变成了10次。由于操作1是有限的，所以优先添加对答案ans减少量贡献大的边，也就是将边按照$min(h[a],h[b])min(h[a],h[b])$从大到小排序，然后依次添加。
• 用并查集维护两个点是否在一个连通块中

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 5e5 + 10, M = 5e6 + 10;
int n, m;
int p[N];
int height[N];

int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}

struct Edge
{
    int a, b, w;
    bool operator<(const Edge &W) const
    {
        return w > W.w;
    }
} edges[M];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        cin >> height[i];
        ans += height[i];
    }

    for (int i = 0; i < m; i++)
    {
        cin >> edges[i].a >> edges[i].b;
        edges[i].w = min(height[edges[i].a], height[edges[i].b]);
    }

    sort(edges, edges + m);

    int cnt = min(5 * n, m);

    for (int i = 0; i < m; i++)
    {
        if (cnt == 0)
            break;
        int a = edges[i].a, b = edges[i].b;
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            ans -= edges[i].w;
            cnt--;
        }
    }
    cout << ans << '\n';
    return 0;
}