B 小沙的魔法

思路

首先，将问题转化为：将高度为 $h_{i}$ 的城市降为0
如果不进行合并操作，需要进行 $ans=\sum _{i=1} ^ {n}h_i$ 次操作2
对每条边 $a - b (a 和 b 为城市编号)$ , 如果将 $a 和 b$ 连接, 那么操作次数就会减少 $m i n (h [a], h [b])$ ，比如高10和高5的城市相连，原本需要15次操作，连接后节约了min(10,5)次，变成了10次。由于操作1是有限的，所以优先添加对答案ans减少量贡献大的边，也就是将边按照 $m i n (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;
}

题解 | #小沙的魔法#

B 小沙的魔法

思路

代码