Codeforces Round #764 (Div. 3) G - MinOr Tree (最小生成树变形，位运算)

Codeforces Round #764 (Div. 3) G - MinOr Tree (最小生成树变形，位运算)

题目链接：https://codeforces.com/contest/1624/problem/G

题目大意
n 个点 m 条边的无向连通图，求所有生成树中，边权或运算的最小值。

思路
二进制位下，从高位到低位枚举，在不使用当前位的情况下是否可以构成生成树

如果可以，则当前位不贡献答案如果不可以，说明一定需要当前位，

详解参考代码

ACcode

#include
#define ll long long
#define endl "n"
using namespace std;

int v[maxn], u[maxn], w[maxn];
int fa[maxn];
vector a[50];
bool vis[maxn], tmp[maxn];

int find(int x){
	if(fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}

void join(int x, int y){
	int fx = find(x);
	int fy = find(y);
	if(fx != fy){
		fa[fx] = fy;
	}
}

int main(){

	int ncase;
	scanf("%d", &ncase);
	
	while(ncase--){
		int n, m;
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= m; i++) scanf("%d %d %d", &u[i], &v[i], &w[i]);
		for(int i = 0; i <= 30; i++){
			for(int j = 1; j <= m; j++){
				if((w[j]>>i)&1){
					a[i].push_back(j);
				}	
			}
		}
		int res = 0;
		for(int i = 30; i >= 0; i--){ // 从高位到低位枚举
			for(int j : a[i]) tmp[j] = 1; // 标记不使用具有当前位的边
			for(int j = 1; j <= n; j++) fa[j] = j;
			for(int j = 1; j <= m; j++){
				if(vis[j] || tmp[j]) continue; // 当前位不使用的边和高位不使用的边
				join(u[j], v[j]);
			}
			int flag = 1;
			for(int j = 1; j <= n; j++){
				if(find(1) != find(j)){
					flag = 0; // 构不成生成树
				}
			}
			if(flag) for(int j = 1; j <= m; j++) vis[j] |= tmp[j]; // 可以构成生成树，标记永久不使用这些边
			else res |= (1<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702698.html