[CF888G]Xor-MST

题目大意：给一个$n$个点的完全图，第$i$个点有点权$v_i$，一条边$x-y$的边权为$v_x\oplus v_y$，求最小生成树

题解：明显$Kruskal$和$Prim$都会$TLE$，有一种别的生成树的算法为$Sollin$。它对棵树找到离它最近的不连通的一棵树，对每棵树找好后若可以连这一条边就连接这条边。可以证明每次连通块个数至少减少一半，每次找最近的树可以枚举每一条边，复杂度$O(m)$，所以总复杂度是$O(m\log_2 n)$的。

在这一题中，可以用$Trie$来优化找最近的树的过程，可以优化为$O(\log_2 v)$，可以通过本题

卡点：发现两个点点权相同就不会产生贡献，于是就可以排序去重，记录最开始连通块个数时记录的是没有去重的点数，于是就一直连不完，一直$TLE$

C++ Code：

#include <algorithm>

#include <cctype>

#include <cstdio>

namespace __IO {

	namespace R {

		int x, ch;

		inline int read() {

			ch = getchar();

			while (isspace(ch)) ch = getchar();

			for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);

			return x;

		}

	}

}

using __IO::R::read;

#define maxn 200010

const int inf = 0x3f3f3f3f;

namespace Trie {

#define M 29

#define N (maxn * (M + 2))

	int V[N], nxt[2][N], root, idx;

	void modify(int x, int num = 1) {

		int p = root;

		for (register int i = M; ~i; i--) {

			int tmp = x >> i & 1;

			if (!nxt[tmp][p]) nxt[tmp][p] = ++idx;

			p = nxt[tmp][p];

			V[p] += num;

		}

	}

	int query(int x) {

		int p = root, res = 0;

		for (register int i = M; ~i; i--) {

			int tmp = x >> i & 1;

			if (V[nxt[tmp][p]]) p = nxt[tmp][p];

			else p = nxt[!tmp][p], res |= 1 << i;

		}

		return res;

	}

#undef N

#undef M

}

int n, num;

std::pair<int, int> M[maxn];

int s[maxn], rnk[maxn];

long long ans;

int f[maxn];

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

inline bool cmp(int a, int b) {return f[a] < f[b];}

int main() {

	n = read();

	for (int i = 1; i <= n; i++) s[i] = read();

	n = (std::sort(s + 1, s + n + 1), std::unique(s + 1, s + n + 1) - s - 1);

	for (int i = 1; i <= n; i++) {

		rnk[i] = f[i] = i;

		Trie::modify(s[i]);

	}

	num = n - 1;

	while (num) {

		for (int i = 1; i <= n; i++) find(i);

		std::sort(rnk + 1, rnk + n + 1, cmp);

		for (int i = 1; i <= n; i++) M[i] = std::make_pair(i, inf);

		for (int l = 1, r, father; l <= n; l = r + 1) {

			father = f[rnk[r = l]];

			while (r < n && father == f[rnk[r + 1]]) r++;

			for (int i = l; i <= r; i++) Trie::modify(s[rnk[i]], -1);

			for (int i = l; i <= r; i++) {

				int val = Trie::query(s[rnk[i]]), pos = std::lower_bound(s + 1, s + n + 1, s[rnk[i]] ^ val) - s;

				if (val < M[father].second) M[father] = std::make_pair(pos, val);

			}

			for (int i = l; i <= r; i++) Trie::modify(s[rnk[i]]);

		}

		for (int i = 1; i <= n; i++) {

			int x = find(i), y = find(M[i].first);

			if (x != y) {

				f[x] = y;

				ans += M[i].second;

				num--;

			}

		}

	}

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

	return 0;

}

巴特西

[CF888G]Xor-MST

最新文章

热门文章