CF1624G 题解

前言

题目传送门！

更好的阅读体验？

比较好玩的二进制题目。

思路

答案最小，也就是说较高位要尽可能小。所以很容易想到从最高位开始枚举。

第 \(i\) 位为 \(0\)，等价于选出的所有边的第 \(i\) 位都为 \(0\)。同时，由于我们是贪心，如果之前枚举过的第 \(j\) 位可以是 \(0\)，那么这两个条件要同时满足。

那么怎样才算第 \(i\) 位可以是 \(0\) 呢？将不满足上述要求的边都排除掉，如果剩下的边可以使得图联通的话，说明必然有一种生成树是合法的，统计即可。

实现并不困难，使用并查集实现。不满足的用一个 \(vis_i\) 记录即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5 + 5;
struct Edge {int now, nxt;} e[N << 1];
int head[N], cur;
void add(int u, int v)
{
	e[++cur].now = v, e[cur].nxt = head[u];
	head[u] = cur;
}
bool used[N], vis[N]; int vist;
void dfs(int u)
{
	vist++, vis[u] = true;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (!vis[v]) dfs(v);
	}
}
int uu[N], vv[N], ww[N];
void solve()
{
	int n, m, ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) scanf("%d%d%d", &uu[i], &vv[i], &ww[i]), used[i] = false;
	for (int j = 30; ~j; j--) //从高到低枚举每一位 
	{
		cur = 0; for (int i = 1; i <= n; i++) head[i] = 0;
		vist = 0; for (int i = 1; i <= n; i++) vis[i] = false;
		
		for (int i = 1; i <= m; i++)
			if (!used[i] && !(ww[i] & (1 << j)))
				add(uu[i], vv[i]), add(vv[i], uu[i]);
		dfs(1);
		if (vist != n) ans += (1 << j); //不是连通的
		else
		{
			for (int i = 1; i <= m; i++)
				if (ww[i] & (1 << j))
					used[i] = true;
		}
	}
	printf("%d\n", ans);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

希望能帮助到大家！