1. 从一道题看最小生成树的本质Clarke and MST 这个标题第一次看到的时候我以为是某位选手的ID加上一道模板题点进去才发现里面藏着一个挺有意思的变形。题目大意是给定一张图每条边有一个权值要求找出一棵生成树使得所有边权按位与AND之后的值最大。这个按位与最大的目标和传统的最小生成树边权和最小完全不是一个路子所以直接套Kruscal模板是过不了的得先想清楚这个目标函数的性质。我先把结论摆出来按位与运算有一个关键性质——高位优先。也就是说二进制下如果第k位能变成1那么哪怕后面所有低位全是0结果也比第k位是0、后面全是1要大。这个性质直接决定了贪心策略的可行性我们从高位到低位逐位尝试看能不能构造出一棵生成树使得当前这一位以及之前已经确定为1的高位在最终结果里保持为1。具体做法是从第30位或者根据权值范围取更高位开始往下枚举维护一个当前允许使用的边集。对于第i位我们只保留那些权值在第i位为1的边然后在这个边集上跑Kruscal看能不能形成一棵生成树。如果能说明这一位可以贡献到最终答案里答案加上这一位同时把边集更新为这个子集如果不能说明这一位无论如何都保不住答案这一位就是0边集不变继续看下一位。这个思路为什么对因为按位与的结果只关心哪些位最终是1。我们贪心地从高位往低位确定每次只在能形成生成树的前提下保留这一位为1的边这样高位一旦确定就不会被低位影响符合按位与高位优先的特性。而Kruscal在这里的作用就是判断当前边集能否构成生成树——只要能选出n-1条边且不形成环就说明可以。2. 并查集在其中的角色与实现细节并查集在这道题里承担的是连通性判定的职责。Kruscal的核心就是按边权排序后依次加边用并查集判断加入这条边会不会成环。但在这道题里我们其实不需要对边排序——因为我们的目标不是最小化边权和而是判断当前边集能否构成生成树。所以Kruscal的排序这一步可以省掉直接遍历边集能加就加最后看加入了多少条边。不过这里有个细节需要注意每次尝试某一位时并查集必须重新初始化。因为上一位的连通状态和这一位要用的边集不一定兼容不能复用。我见过有人为了省事在循环外面初始化一次并查集结果WA到怀疑人生。这个坑很典型因为并查集的parent数组是会被路径压缩修改的复用会导致连通性判断完全错乱。并查集的实现我用的是带路径压缩的版本没有加按秩合并因为这道题的数据规模通常不会太大n和m一般在1e5以内路径压缩已经足够把单次find的均摊复杂度压到接近常数。如果你追求极致性能可以加上按秩合并但实际测下来差别不大。int parent[100005]; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; parent[ra] rb; return true; }上面这段代码是并查集的核心。注意find里的路径压缩写法递归版本在数据量大时可能爆栈可以改成迭代版本。我在实际写的时候习惯用迭代虽然代码稍微长一点但心里踏实。3. 逐位贪心的完整实现与参数选择现在把整个算法的流程串起来。假设边权最大不超过2^30那么我们从第30位枚举到第0位。每一位的处理分三步第一步把当前边集中所有第i位为1的边筛选出来形成候选边集第二步用并查集在候选边集上跑Kruscal统计能加入的边数第三步如果加入的边数等于n-1说明这一位可以保留答案加上(1i)同时把当前边集更新为候选边集否则这一位放弃边集不变。这里有一个容易忽略的点边集的更新时机。只有在当前位能形成生成树时我们才把边集缩小到候选边集。如果这一位不能形成生成树我们继续用原来的边集去看下一位。这个逻辑保证了我们不会因为某一位保不住而丢失更高位已经确定的信息。关于枚举的起始位我一般取30因为大多数题目的边权在int范围内。如果边权可能达到long long范围那就取60。但实际比赛中30位已经足够覆盖绝大多数情况。如果你不确定可以先把所有边权的最大值求出来然后取它的最高位作为起始位这样能省掉一些无用的枚举。int n, m; struct Edge { int u, v, w; } edges[200005]; int solve() { int ans 0; vectorEdge cur(edges, edges m); for (int bit 30; bit 0; bit--) { vectorEdge nxt; for (auto e : cur) { if (e.w bit 1) nxt.push_back(e); } // 初始化并查集 for (int i 1; i n; i) parent[i] i; int cnt 0; for (auto e : nxt) { if (unite(e.u, e.v)) cnt; } if (cnt n - 1) { ans | (1 bit); cur nxt; } } return ans; }这段代码是整个解法的骨架。注意里面用vector来维护当前边集每次筛选后如果可行就替换。这样做的好处是逻辑清晰缺点是每次都要复制vector在m很大的时候会有性能开销。如果追求极致可以用一个标记数组来标记哪些边还在当前边集中避免复制。但一般来说m在1e5以内时vector的复制开销是可以接受的。4. 复杂度分析与常见错误排查这个算法的时间复杂度是O(30 * (m n))因为每一位都要遍历当前边集跑一次Kruscal而Kruscal的复杂度主要取决于边数和并查集操作。30是常数所以整体可以认为是O(m n)的级别对于1e5的数据规模来说完全够用。空间复杂度是O(m n)主要是存储边和并查集数组。常见错误我整理了一个速查表这些都是我在做题和帮别人debug时反复见到的错误类型具体表现原因修正方法并查集未重置答案偏小或偏大上一位的连通状态污染了当前位每次尝试新位前重新初始化parent数组边集更新时机错误答案偏小在不能形成生成树时也更新了边集只在cntn-1时更新cur枚举位数不够答案偏小边权超过2^30时高位丢失根据最大边权确定起始位生成树判定条件错误答案偏大用cntn-1判断但cnt不可能超过n-1严格判断cntn-1递归find爆栈运行时错误数据量大时递归深度过深改用迭代版本find其中并查集未重置是最容易犯的错因为写惯了模板题的人会下意识觉得并查集初始化一次就行。但这道题的逻辑决定了每次尝试新位都是一次独立的连通性判定必须重置。还有一个细节如果图本身不连通那么无论怎么选边都无法形成生成树最终答案应该是0。这个情况在代码里自然处理了——因为cnt永远达不到n-1ans保持为0。但有些题目会保证图连通所以这个边界情况不一定能测到自己写的时候心里要有数。5. 从这道题延伸出的思考这道题表面上是Kruscal加并查集的组合但真正有意思的地方在于它把最小生成树的框架用在了按位与最大这个完全不同的目标上。Kruscal在这里退化成了一个连通性判定工具排序步骤被完全跳过这是很多人一开始想不到的。我后来在想如果目标改成按位或最大或者按位异或最大思路会不会不一样按位或的话高位优先的性质依然成立但贪心策略可能需要调整因为或运算下某一位为1的边可能不止一条选择哪一条会影响后续。按位异或就更复杂了因为异或没有单调性高位优先不成立得换别的思路。这些问题没有标准答案但拿来锻炼思维挺好的。另外这道题也提醒我模板题做多了容易形成思维定式。看到生成树就想到Kruscal看到Kruscal就想到排序但实际题目往往会在某个环节做变形。真正重要的是理解每个算法组件解决的是什么问题——Kruscal解决的是在边集上选出一棵生成树并查集解决的是动态连通性判定至于边怎么排序、按什么顺序加那是可以根据题目目标灵活调整的。我在实际写这道题的时候第一次提交WA了就是因为并查集没有重置。后来改过来之后又发现枚举位数只到20导致大权值的边被忽略。这两个坑踩完之后这道题才算真正吃透了。现在回头看这道题的价值不在于它有多难而在于它逼着你去思考每个算法步骤的必要性——排序真的必要吗并查集的状态能不能复用这些问题想清楚了对Kruscal和并查集的理解会上一个台阶。