「UOJ 176」新年的繁荣

tulipenoire / 2024-10-09 / 原文

由于不会 B 姓最小生成树算法，所以只能用 Kruskal 做了。但是好像非常简洁。

有一个小贪心就是相同点权的直接连起来肯定不劣。因为不会浪费。那么接下来问题就是每种值只有一个。

考虑从大到小枚举边权 $v$。那么我们现在要做的就是把所有 $x \& y = v$ 并且不在同一个集合中的 $x$ 和 $y$ 合并。考虑这样一个事实：将边权 $v$ 的对应合并操作执行完过后，$v$ 的所有超集肯定都在同一集合内。这意味着我们只需要枚举 $v|2^k$ 执行完后的那个集合然后将其合并即可。

时间复杂度 $\mathcal O(n+2^mm)$，代码极其好写。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 100005, M = 18;
int n, m, fa[1 << M], g[1 << M];
int Find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = Find(fa[x]);
} 
inline void Merge(int x, int y) {
	fa[Find(x)] = Find(y);
}
int main() {
	memset(g, -1, sizeof g);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < (1 << m); i++) fa[i] = i;
	LL outp = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		if (~g[x]) outp += x;
		else g[x] = x;
	}
	for (int i = (1 << m) - 1; i; i--) {
		int now = g[i];
		for (int j = 0; j < m; j++) {
			int k = g[i | (1 << j)];
			if (!~k) continue;
			if (!~now) now = k;
			else {
				if (Find(now) != Find(k)) outp += i, Merge(now, k);
			}
		}
		g[i] = now;
	}
	printf("%lld", outp);
	return 0;
}