Codeforces周赛 #764 (Div.3)：G. MinOr Tree（最小或树）_codeforces 最小生成树

CF周赛div3：G. MinOr Tree（最小生成树的变种 —— 最小或树）

题意：

• 给定 n 个点 m 条边，要求构建出一颗树，树上所有边权值 或 起来最小

与普通的最小生成树不同，要求 或运算 的最小树，显然与二进制相关

所以我们观察下二进制下的状态，可以发现：

• 要求 或起来 的结果尽可能小，树上的边的二进制高位就要尽可能都为 0

• 所以我们可以贪心地去取边，从二进制高位枚举到低位，判断只选取此位为 0 的边能否形成一棵树；若能，那最终结果的 二进制该位 肯定也为 0，此位为 1 的边全部都标记（舍弃了），在之后的枚举中不会使用；否则此位不可能满足，查看下一位

• 如此就能构建出这颗特殊生成树

注意位运算的一些细节

代码：

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define fx first
#define fy second
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair <ll, PII> PI;

const int N = 200010, M = 500010, MM = N;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int p[N];
struct edge
{
	int a, b, w;
}ed[M];
bool st[M];
vector<int> v;

int find(int x) {
	if (p[x] != x)p[x] = find(p[x]);
	return p[x];
}

bool check(int j) {
	v.clear();
	for (int i = 1; i <= n; i++)p[i] = i;//初始化

	int cnt = 0;
	for (int i = 0; i < m; i++) {
		if (st[i])continue;//舍弃过的边
		int a = ed[i].a, b = ed[i].b, w = ed[i].w;

		if (w >> j & 1) { //该位为 1
			v.push_back(i);
			continue;
		}

		if (find(a) ^ find(b)) { //该位为 0 的边构树
			p[find(a)] = find(b);
			cnt++;
		}
	}
	if (cnt == n - 1)return true;//满足是颗树
	return false;
}

int main() {
	cinios;

	cin >> T;
	while (T--)
	{
		cin >> n >> m;
		mem(st, 0);
		int ans = (1 << 31) - 1;//二进制状态下 31 个 "1"
		//虽然(1 << 31)已经超出了int型，但只溢出了 1

		for (int i = 0; i < m; i++) {
			int a, b, x;
			cin >> a >> b >> x;
			ed[i] = { a,b,x };
		}

		for (int j = 30; j >= 0; j--)//枚举二进制位，高位到低位
			if (check(j)) {
				for (auto t : v)st[t] = true;
				//如果能用该位为 0 的边构成树，为 1 的边就可以舍弃了

				ans -= 1 << j;
				//1 本身在二进制状态下就是一位
				//左移 j 位，第 j + 1 位变成 "1"。其余都是 "0"
			}

		cout << ans << '\n';
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91