A 并查集 (正难则反)

题意

给你一个图，上面有点值，你可以选一个联通子图，将上面点的点值减一。问至少要操作多少次，才能使整个图的点值为 0

思路

刚开始肯定是想一些很暴力的手段，假设 G 是一个连通图。

  1. 每次找到 $G$ 的最小点权 $v.weight$，对应的点为 $v$，答案贡献 $ans += v.weight$
  2. $G = G - v$，$G$ 每个点的点权减 $v.weight$
  3. $G$ 为空，算法结束，否则执行 1.

这个方法太暴力了，看上去很不可做。

那么我们不妨把上面的过程倒过来：

  1. $G’$ 为空，原图为 $G$
  2. 从 $G$ 中选一个最大点权 $v.weight$，对应的点为 $v$，$G = G - v$，$G’ = G’ + v$
  3. 记 $G’$ 中的最小点权为 $u.weight$，对应的点为 $u$ , $ans += v.weight - u.weight$，表示使 $G’$ 内的点权一样，至少执行多少次减法
  4. 若 $G$ 为空，算法结束，否则执行 2.

最后我们将 $G’$ 的点权清零 $ans += min(G)$

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5, M = 2e5 + 5;
struct edge {int to, next;} edges[M << 1];
int head[N], a[N], tot;

int fa[N], id[N];
bool disable[N];

void init(int n) {
    memset(head + 1, -1, sizeof(int) * n);
    iota(fa + 1, fa + n + 1, 1);
    iota(id + 1, id + n + 1, 1);
    memset(disable + 1, true, n);
    tot = 0;
}

void add_edge(int u, int v) {
    edges[tot] = {v, head[u]};
    head[u] = tot++;
}

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

int main() {
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        init(n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);

        sort(id + 1, id + 1 + n, [](int x, int y) {
            return a[x] > a[y];
        });

        for (int i = 1; i <= m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
        }

        ll ans = 0;
        for (int i = 1; i <= n; ++i) {
            int u = id[i];
            disable[u] = false;
            for (int j = head[u]; ~j; j = edges[j].next) {
                int v = edges[j].to, fv = find(v);
                if (disable[v] || fv == u) continue;
                ans += a[fv] - a[u];
                fa[fv] = u;
            }
        }

        for (int i = 1; i <= n; ++i)
            if (find(i) == i) ans += a[i];

        printf("%lld\n", ans);
    }
}