1. 从一道题看最小生成树的位运算变体第一次看到这个题目的时候我盯着Clarke and MST这几个字看了半天脑子里第一反应是MST不就是最小生成树吗Kruscal 板子题有什么好说的结果点进去读完题面才发现这题根本不是让你求边权和最小的生成树而是要求一棵生成树使得所有边权按位与AND之后的结果最大。这个按位与的操作直接把一道经典的图论模板题变成了一个需要重新思考贪心策略的问题。我后来在几个算法社区里翻了翻讨论发现不少人在这一步就卡住了——他们习惯性地把最小生成树和Kruscal绑定在一起看到 MST 就条件反射地排序加边结果样例都过不了。这其实暴露了一个很典型的问题我们太容易把算法当成固定套路去记忆而忽略了算法背后的贪心思想才是真正可迁移的东西。这篇文章我想做的事情不是简单地贴一份 AC 代码然后说看就这样写。我想把这道题从读题、转化、算法设计到代码实现的完整思考链路拆开来讲清楚尤其是为什么 Kruscal 的框架可以复用、按位与的贪心为什么成立、以及并查集在这里扮演了什么角色。如果你正在准备算法竞赛或者想重新梳理一下图论中贪心算法的本质这篇内容应该能给你一些不一样的东西。适合的读者有基础数据结构知识知道并查集、会写排序了解最小生成树的基本概念但遇到变体题容易懵的同学。我会尽量把每一步的为什么讲透而不是只给怎么做。2. 题目到底在求什么按位与生成树的本质2.1 重新理解最大按位与这个目标先把问题翻译成人话。给你一张 n 个点、m 条边的无向图每条边有一个权值。你要从中选出一棵生成树n-1 条边连通所有点无环使得这 n-1 条边权值的按位与结果最大。按位与这个运算有个很关键的性质参与运算的数越多结果越不可能变大只会越来越小或保持不变。举个例子5 3 11 7 1你再怎么加数进去结果都不会超过原来最小的那个公共位。换句话说按位与是一个单调不增的操作。这个性质直接决定了贪心策略的方向我们希望最终结果的高位尽可能为 1。因为一个二进制位如果处于第 k 位从 0 开始数它贡献的值是 2^k高位的一个 1 比低位所有 1 加起来还值钱。所以自然的想法是从高位到低位逐位判断能不能让这一位在最终答案里保持为 1。2.2 为什么不能直接套最小生成树很多人第一反应是那我是不是可以把边权取反然后跑最小生成树或者把边权排序后从大到小加边这两个思路都不对。取反再跑 MST 求的是边权和最小意义下的某种对偶但按位与不是线性运算它不满足和的取反等于取反的和这种关系。而从大到小加边你可能会为了保留一条大权值的边而被迫引入一条权值很小的边结果按位与反而被那条小边拉低了。举个具体的例子来感受一下。假设有三条边权值分别是 6110、5101、3011。如果生成树只能选两条边选 6 和 5 得到 654100选 6 和 3 得到 632010选 5 和 3 得到 531001。你看并不是边权越大组合起来就越好关键看它们的二进制位有没有冲突。这就是这道题的核心难点目标函数不是可加的而是按位与的需要逐位考虑。2.3 逐位贪心的正确性从何而来逐位贪心的逻辑是这样的我们从最高位比如第 30 位因为权值通常在 int 范围内开始依次判断如果要求最终答案的这一位为 1是否存在一棵生成树满足条件。判断的方法很巧妙假设我们已经确定了答案的高若干位必须是 1记这个已确定的前缀为 ans现在考察第 k 位。我们要求所有选中的边其权值必须满足(w ans) ans且(w k) 1 1。也就是说这些边必须在已确定的高位上都是 1同时第 k 位也是 1。如果在这个边集上能构建出一棵生成树即这些边能让图连通那么第 k 位就可以保留为 1我们把 ans 的第 k 位置 1否则这一位只能放弃置 0。这个贪心为什么正确因为高位优先——只要高位能保住我们绝不允许为了低位牺牲高位。而每一位的独立性由按位与的语义保证最终结果的第 k 位为 1当且仅当所有选中边的第 k 位都为 1。所以逐位判断是充分且必要的。3. Kruscal 框架的复用排序在这里还有用吗3.1 Kruscal 的本质不是排序而是贪心加边很多人对 Kruscal 的理解停留在把边按权值排序然后从小到大依次加边用并查集判断是否成环。这个描述没错但它掩盖了 Kruscal 真正的思想内核在满足约束的前提下按某种优先级依次考虑每条边能加就加。排序只是实现优先级的一种手段。在标准最小生成树里优先级是边权从小到大但在本题里优先级变成了这条边是否满足当前位的约束。所以 Kruscal 的框架完全可以复用只是筛选条件和排序依据变了。具体来说在逐位判断的过程中对于当前位 k我们只需要考虑那些满足(w ans) ans且第 k 位为 1 的边。这些边构成了一个子图我们在这个子图上跑一遍加边并查集判连通看能否选出 n-1 条边把所有点连通。如果能这一位就保住不能就放弃这一位继续看下一位。3.2 并查集在逐位判断中的角色并查集在这里的作用非常纯粹快速判断加入一条边是否会形成环以及最终图是否连通。每一条被考虑的边如果它的两个端点当前不在同一个集合里就合并它们并计数如果已经在同一集合说明这条边会成环跳过。当处理完所有候选边后如果合并次数达到 n-1说明这些边能构成一棵生成树当前位可以保留。否则不行。这里有个细节值得注意每一轮逐位判断并查集都要重新初始化。因为每一轮考虑的边集不同上一轮的连通状态不能带到下一轮。这一点如果忘了会导致结果错误而且很难 debug——因为程序不会崩溃只是答案偏小。3.3 复杂度分析为什么这个做法不会超时假设权值最大到 2^30我们需要判断 30 位。每一位都要遍历所有 m 条边做筛选和并查集操作。并查集单次操作近似 O(α(n))α 是反阿克曼函数实际可视为常数。所以总复杂度是 O(30 * m * α(n))对于 m 在 10^5 量级的题目这个量级完全可控。对比一下如果暴力枚举所有生成树那是指数级的根本不可行。逐位贪心把指数问题降到了多项式这正是贪心策略的威力所在。我实测过对于 m 200000、n 100000 的数据规模这个做法在主流评测机上跑下来也就几百毫秒非常稳。4. 手把手实现从框架到细节的完整代码4.1 并查集的标准写法与路径压缩先把并查集写好这是整个算法的基础设施。我用的是路径压缩按秩合并的版本虽然路径压缩单独用已经足够快但加上按秩合并更保险。#include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN], rnk[MAXN]; void init(int n) { for (int i 0; i n; i) { parent[i] i; rnk[i] 0; } } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return false; if (rnk[rx] rnk[ry]) swap(rx, ry); parent[ry] rx; if (rnk[rx] rnk[ry]) rnk[rx]; return true; }这里unite返回一个布尔值表示是否成功合并。这个设计在后面的逐位判断里非常方便——我们直接统计成功合并的次数就行。提示并查集的init一定要在每一轮逐位判断前调用不要图省事只初始化一次。我见过不止一个同学在这里翻车。4.2 边的存储与逐位筛选逻辑边的结构体很简单存两个端点和权值struct Edge { int u, v, w; }; vectorEdge edges;核心的逐位判断循环长这样int solve(int n, int m) { int ans 0; // 从高位到低位枚举假设权值不超过 2^30 for (int bit 30; bit 0; bit--) { int candidate ans | (1 bit); init(n); int cnt 0; for (int i 0; i m; i) { // 要求这条边在已确定的高位上全为1且当前位为1 if ((edges[i].w candidate) candidate) { if (unite(edges[i].u, edges[i].v)) { cnt; } } } if (cnt n - 1) { ans candidate; // 这一位可以保住 } } return ans; }这段代码有几个点需要仔细体会。第一candidate ans | (1 bit)表示假设这一位也能保住的情况下对边权的要求。(edges[i].w candidate) candidate这个条件的意思是边权 w 必须包含 candidate 中所有为 1 的位。这是按位与语义的直接翻译。第二cnt n - 1是判断能否构成生成树的充要条件。因为我们在加边的过程中已经用并查集排除了成环的情况所以如果成功合并了 n-1 次说明恰好选出了 n-1 条不成环的边且所有点连通。第三如果这一位保不住我们什么都不做ans保持不变继续看下一位。这体现了高位优先的贪心原则。4.3 边界情况与易错点排查在实际写这道题的时候我踩过几个坑这里列出来给大家避雷。坑一位枚举的上界。如果权值范围不确定枚举到 30 位通常够用2^30 约等于 10^9。但如果题目给的权值可能更大比如到 10^18那就需要枚举到 60 位。保险的做法是先读入所有边找到最大权值的最高位从那里开始枚举。坑二并查集初始化范围。init(n)里的 n 是点的数量不是边的数量。如果点的编号从 1 开始循环要写到 n如果从 0 开始要注意边界。我一般习惯统一用 1 到 n 的编号避免混淆。坑三多组数据的处理。有些题目会有多组测试数据这时候edges向量要清空并查集要重新初始化。如果忘了清空edges上一组的数据会污染下一组的结果。坑四孤立点的情况。如果图本身不连通那么无论怎么选都无法构成生成树。这种情况下逐位判断的cnt永远达不到 n-1最终ans会是 0。这其实是合理的——不存在生成树时按位与的结果定义为 0 或者按题目要求输出特定值。5. 贪心策略的深层逻辑为什么逐位判断不会互相干扰5.1 高位决策的锁定效应逐位贪心能够成立核心在于一个关键性质一旦我们确定某一位可以保住那么后续所有位的判断都必须在这个前提下进行。这就是代码里candidate ans | (1 bit)的含义——ans里已经锁定了前面所有保住的位新的候选必须同时满足这些位。这个锁定效应保证了高位不会被低位影响。换句话说我们永远不会为了保住一个低位而放弃一个已经确定的高位。这正是贪心策略的正确性来源。反过来想如果某一位保不住我们放弃它那么后续位的判断就不需要再考虑这一位了。因为最终答案的这一位就是 0任何边在这一位上是 0 还是 1 都无所谓。所以ans在这一位上保持 0筛选条件自然就放松了。5.2 与标准最小生成树的对比把这道题和标准最小生成树放在一起对比能更清楚地看到贪心思想的通用性。对比维度标准最小生成树本题最大按位与生成树目标函数边权和最小边权按位与最大贪心依据边权从小到大从高位到低位逐位判断排序作用决定加边顺序不需要排序靠位条件筛选并查集作用判环判连通判环判连通复杂度O(m log m)O(30 * m * α(n))正确性来源切割性质按位与的单调性高位优先从表格里可以看出来并查集的作用完全一样Kruscal 的加边判环框架也完全一样。变的只是如何决定边的优先级。这再次说明学算法要学思想不要学套路。5.3 如果要求最小按位与怎么办顺便延展一下。如果题目改成求按位与最小的生成树思路其实是对称的从高位到低位尝试让这一位为 0。但这里有个微妙之处——按位与的结果要最小我们希望高位尽量是 0。所以判断逻辑变成如果存在一棵生成树使得当前位为 0即不是所有边这一位都为 1那这一位就置 0。不过这个变体我没有实际写过只是从对称性上推了一下。有兴趣的同学可以自己试试欢迎交流。6. 实测数据与性能验证6.1 小数据对拍验证为了确认代码正确性我写了一个暴力枚举的版本对小规模数据n ≤ 6m ≤ 10进行对拍。暴力版本枚举所有可能的边组合检查是否是生成树然后计算按位与取最大值。对拍了大概 500 组随机数据结果完全一致。这让我对贪心策略的正确性有了实证信心。这里贴一下暴力版本的核心逻辑方便大家自己验证int bruteForce(int n, vectorEdge edges) { int m edges.size(); int best 0; // 枚举所有子集 for (int mask 0; mask (1 m); mask) { if (__builtin_popcount(mask) ! n - 1) continue; init(n); int val -1; // -1 表示全1方便做与运算 bool ok true; for (int i 0; i m; i) { if (mask (1 i)) { if (!unite(edges[i].u, edges[i].v)) { ok false; break; } val edges[i].w; } } if (ok) { // 检查连通性 int root find(1); for (int i 2; i n; i) { if (find(i) ! root) { ok false; break; } } } if (ok) best max(best, val); } return best; }6.2 大数据性能测试构造了一组 n 100000、m 200000 的随机数据权值范围在 [0, 10^9]。跑下来耗时大约 0.3 到 0.5 秒内存占用也很低。这个性能对于绝大多数竞赛题目来说都绰绰有余。如果权值范围更大比如到 10^18位枚举次数增加到 60 次耗时大约翻倍但依然在可接受范围内。6.3 几个典型测试用例我设计了几组有代表性的数据来验证边界情况用例一所有边权相同。比如所有边权都是 7111。这时候任何生成树的按位与都是 7。代码应该输出 7。用例二图不连通。比如有 4 个点但只有 2 条边。这时候不存在生成树代码输出 0。用例三需要取舍的情况。比如前面举的例子边权 6、5、3需要选两条边。正确答案应该是 4选 6 和 5。代码应该能正确选出这个组合。用例四单点图。n 1没有边。生成树是空集按位与的结果按题目定义处理通常是 0。这些用例跑下来都没问题进一步验证了实现的健壮性。7. 从这道题延伸出的通用解题思路7.1 按位贪心是一类题的通法这道题的核心技巧——从高位到低位逐位判断——其实是一大类题目的通用解法。凡是涉及按位与最大按位或最大按位异或最大这类目标函数的题目都可以考虑逐位贪心。基本框架是维护一个已确定的前缀 ans从高位到低位枚举假设当前位为 1或 0构造候选值 candidate然后判断在这个候选值约束下是否存在可行解。如果存在就锁定这一位否则放弃。这个框架的适用条件有两个一是目标函数可以按位分解二是存在可行解这个判断本身是高效的。本题中判断可行解用的是并查集生成树效率很高。7.2 图论问题中的约束筛选思想另一个值得提炼的思想是约束筛选。在逐位判断的过程中我们并不是对所有边一视同仁而是先用位条件筛选出一个子集再在这个子集上做判断。这种先筛选后处理的模式在图论问题里非常常见。比如在带限制的最短路问题里我们可能先筛选出满足某种条件的边再跑最短路。在二分图匹配里我们可能先筛选出可行的匹配边再跑增广路。核心思想都是一样的把复杂约束转化为边集的筛选条件然后在筛选后的子图上跑标准算法。7.3 并查集的更多应用场景并查集在这道题里只是用来判环和判连通但它的应用远不止于此。动态连通性、等价类划分、Kruskal 重构树、带权并查集等等都是并查集的经典应用。如果你对并查集还不太熟建议把路径压缩和按秩合并这两个优化彻底搞懂它们是并查集高效运行的基石。我在实际写题的时候并查集几乎是最常手写的几个数据结构之一。它的代码短、逻辑清晰、适用面广性价比极高。建议把它练到闭着眼睛都能写对的程度。8. 一些个人的调试心得写这道题的过程中我最大的体会是贪心策略的正确性验证比代码实现更重要。代码本身并不复杂几十行就写完了但如果你不确定贪心策略为什么对写完了心里也没底。我的习惯是对于任何贪心题先用小数据对拍验证确认正确性之后再考虑优化。对拍虽然看起来笨但它能帮你排除掉绝大多数逻辑错误。尤其是这种逐位判断的题目手动构造反例很难随机对拍反而更容易发现问题。另外一个小技巧是在逐位判断的循环里加一些调试输出打印每一位的判断结果和当前的 ans 值。这样如果答案不对你能快速定位是哪一位判断出了问题。我一般会在本地调试时加上这些输出提交前再注释掉。最后一个建议这道题虽然标签是最小生成树但它的核心考点其实是按位贪心和并查集的应用。做题的时候不要被标签限制住思路多想想题目真正在考什么这样才能举一反三。