【按位贪心代码源每日一题div1】Minimum Or Spanning Tree

￡神魔★判官ぃ 2024-03-16 16:38 45阅读 0赞

[Minimum Or Spanning Tree - 题目 - Daimayuan Online Judge][Minimum Or Spanning Tree - _ - Daimayuan Online Judge]

题意：

![a5952e163a464af18f6598530478510a.png][]

思路：

求最小的生成树，考虑按位贪心，即从高位往低位贪心

对于这类按位贪心问题，一般考虑从高位往低位贪，然后check这位能不能是0/1

对于这道题，因为是最小，所以优先考虑这位能不能贪成0，然后去check

怎么check呢，check函数里，问题就转化为：选一些边，使得不成环且或起来这位是0

Code：

void slove() {
    	cin >> n >> m;
    	vector<edge>e;
    	for (int i = 1; i <= m; i++) {
    		cin >> u >> v >> w;
    		e.push_back({ u,v,w });
    	}
    	int ans = 0;
    	for (int i = 30; i >= 0; i--) {
    		vector<edge>ne;//新的边的集合
    		UF uf = UF(n);
    		for (auto ed : e) {
    			u = ed.u, v = ed.v, w = ed.w;
    			if (((w >> i) & 1) == 0){
    				ne.push_back(ed);
    				uf.Union(u, v);//并查集连接u v
    			}
    		}
    		if (uf.count == 1) {
    			e = ne;//如果仅靠0的边就能联通，删除1的边
    			ans += (0 << i);//为了对称
    		}
    		else {
    			//如果不能联通，答案的这一位只能是1了
    			ans += (1 << i);
    		}
    	}
    	cout << ans << endl;
    }

[Minimum Or Spanning Tree - _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/454
[a5952e163a464af18f6598530478510a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6ef22a9d801a442abb7693ce0df399c3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，45人围观）

还没有评论，来说两句吧...

相关阅读

相关代码源每日一题div1 DP 数组划分

[数组划分 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![3df804eb4f5b4

向右看齐/ 2024年03月31日 13:09/ 0 赞/ 52 阅读

相关代码源每日一题div1 贪心线性筛最小生成数

[最小生成数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![471a3025205c

柔情只为你懂/ 2024年03月31日 12:49/ 0 赞/ 60 阅读

相关代码源每日一题div1 枚举倍数平方计数

[平方计数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![4599c5d594734

小灰灰/ 2024年03月31日 12:35/ 0 赞/ 65 阅读

相关【最坏贪心】代码源每日一题div1 排列 2023.02.03

[排列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 今天牛牛完结撒花辣！但是我还没补完题，感觉这

短命女/ 2024年03月27日 13:01/ 0 赞/ 54 阅读

相关【按位考虑DP】代码源每日一题div1 2023.02.02 与

[与 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 这太酷了，很符合我对DP的想象这DP太妙了

缺乏、安全感/ 2024年03月27日 11:42/ 0 赞/ 59 阅读

相关【代码源每日一题div1】树状数组数数

就是把权值树状数组反过来，感觉很妙啊 [数数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意

蔚落/ 2024年03月26日 19:46/ 0 赞/ 56 阅读

相关【贪心】代码源每日一题div2 背包

[背包 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![c70769545d9f444

浅浅的花香味﹌/ 2024年03月16日 18:13/ 0 赞/ 61 阅读

相关【贪心+权值线段树】代码源每日一题div1 双端队列

感觉难度不如蓝桥杯 [双端队列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![87

桃扇骨/ 2024年03月16日 16:49/ 0 赞/ 53 阅读

相关【按位贪心代码源每日一题div1】Minimum Or Spanning Tree

[Minimum Or Spanning Tree - 题目 - Daimayuan Online Judge][Minimum Or Spanning Tree - _ -

￡神魔★判官ぃ/ 2024年03月16日 16:38/ 0 赞/ 46 阅读

相关【状态设计优化DP】代码源每日一题div1 等差数列

[等差数列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![64f437cfde1a4

我就是我/ 2024年03月16日 14:48/ 0 赞/ 41 阅读