1. 项目概述从一道经典图论题说起如果你正在准备信息学奥赛或者对算法竞赛感兴趣那么“繁忙的都市”这道题你大概率绕不过去。它同时出现在《信息学奥赛一本通》和洛谷P2330上标签是[SCOI2005]。乍一看标题你可能会觉得这是道模拟城市交通的复杂题目但实际上它的内核非常经典且纯粹最小生成树。这道题的价值在于它用一个非常生活化的场景——城市道路改造包装了一个核心的图论算法问题考察的是选手对最小生成树算法本质的理解和灵活应用能力而不仅仅是套模板。这道题描述了一个典型的城市规划问题一个城市有N个交叉路口这些路口之间原本有一些道路相连。现在政府希望进行改造目标是最终保持整个城市的连通性即从任何一个路口都能到达其他所有路口但需要改造的道路数量尽可能少。同时在所有可能的改造方案中他们希望方案里那条最繁忙即通行能力最大的道路其繁忙程度尽可能小。题目会给出所有道路及其对应的“繁忙度”可以理解为通行能力或权重我们需要输出两个答案一是最少需要改造的道路数量二是在满足道路数量最少的前提下方案中繁忙度最大的那条路其繁忙度最小能是多少。我当年第一次碰到这题时觉得条件有点绕。既要路少又要最忙的那条路不那么忙这听起来有点矛盾。但深入分析后就会发现这正是最小生成树性质的完美体现。它不像裸的最小生成树题直接求总权值和而是转换了问题视角重点考察生成树中最大边权的最小化问题。这直接关联到最小生成树的一个关键性质对于无向连通图其所有最小生成树中最大边权的最小值可以通过求取最小生成树来获得并且这个值就是最小生成树中最大的那条边的权值。理解这一点是解开这道题的关键。2. 核心思路拆解为什么是最小生成树很多新手看到“连通”、“边权”这些词可能会想到最短路。但仔细分析题目的两个约束就能把思路引向正轨。2.1 约束条件翻译与建模首先我们把题目的要求翻译成图论语言城市有N个路口对应图中的N个顶点。道路对应图中的边。道路的繁忙度对应边的权值。保持整个城市连通意味着最终留下的边构成的子图必须使原图连通。更准确地说留下的边需要连接所有N个顶点。改造的道路尽可能少在保证连通的前提下边数最少。连接N个顶点的连通图最少需要多少条边答案是N-1条。这正好构成一棵树无环连通图。所以第一个条件直接告诉我们最终方案必然是一棵生成树。在道路数最少即N-1条的前提下使最繁忙的道路尽可能不繁忙这意味着我们要在所有可能的生成树中找到一棵树使得这棵树里权值最大的那条边即max_edge_weight尽可能小。所以问题的核心就变成了给定一个无向连通图求其所有生成树中最大边权最小的那棵树并输出其最大边权的值。同时因为生成树必然有N-1条边所以第一个答案直接就是N-1。题目要求输出这个数更像是一个对结论的验证或者说是解题思路的副产品。2.2 最小生成树性质的运用现在我们需要一个算法能从所有生成树里找出“最大边权最小”的那一棵。这里就要用到最小生成树MST的一个重要性质最小瓶颈生成树性质一棵生成树T是图G的最小生成树当且仅当T是G的“最小瓶颈生成树”。所谓“最小瓶颈生成树”是指这棵生成树中最大边权值是所有生成树中最小的。换句话说求一棵生成树使其最大边权最小等价于求图的最小生成树。最小生成树自动保证了树中最大边权的最小化。这是一个非常优美且实用的结论。因此解题步骤变得极其清晰将城市路口和道路建模为带权无向图。求出该图的一棵最小生成树使用Kruskal或Prim算法。最小生成树的边数一定是 N-1这就是第一个答案。在构建最小生成树的过程中记录下加入树的最后一条边即权值最大的那条边的权值这就是第二个答案。注意这里有一个常见的理解误区。有人会想是不是需要求“最小生成树里最大边权的最小值”听起来像是个双重优化。但根据上述性质对于任意一个无向连通图你只要算出它的任意一棵最小生成树那么这棵树里的最大边权就是所有生成树中可能出现的最大边权的最小值。所以一次最小生成树算法就同时解决了两个问题。2.3 算法选择Kruskal 还是 Prim既然确定了用最小生成树算法接下来就是选择Kruskal还是Prim。对于这道题两者都可以但基于题目常见的输入格式边数M可能较多N一般不超过300我强烈推荐使用Kruskal算法原因如下编码简单Kruskal的核心是排序并查集思路直观不易出错。直接获取答案在Kruskal算法中我们按边权从小到大尝试添加边。当成功添加第 N-1 条边整棵树构建完成时最后添加的那条边的权值自然就是整棵生成树中最大的边权也就是我们需要的第二个答案。这个过程非常自然。效率足够题目规模通常 N≤300, M≤5000或更大Kruskal的复杂度是 O(M log M)完全够用。相比之下Prim算法尤其是朴素版需要维护当前集合到其他点的最小距离在记录最大边权时需要额外处理不如Kruskal直接。实操心得在竞赛中遇到这种明显是MST变种的题除非题目有特殊限制比如稠密图否则优先考虑Kruskal。它的模板固定且易于处理“边”相关的附加问题比如本题的求最大边权。3. 代码实现与细节解析理论清晰后我们来看具体实现。这里以C为例因为这是信息学奥赛的主流语言。我会先给出完整的代码框架然后逐一拆解关键细节。3.1 数据结构定义与输入处理首先我们需要定义边Edge的结构体并准备好并查集。#include iostream #include algorithm using namespace std; const int MAX_M 100005; // 根据题目可能的最大边数设置通常开大一点 struct Edge { int u, v, w; // 路口u路口v繁忙度w } edges[MAX_M]; int father[305]; // 并查集数组N最大300多开几个 int n, m; // n个路口m条道路 // 并查集查找根节点带路径压缩 int find(int x) { if (father[x] ! x) { father[x] find(father[x]); } return father[x]; } // 并查集合并 void unionSet(int x, int y) { int fx find(x); int fy find(y); if (fx ! fy) { father[fy] fx; } } int main() { cin n m; for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } // ... 后续处理 }细节解析边数组大小MAX_M不能开得刚好等于题目给的m最大值。要留有余量一般开成100005或200005是安全的竞赛习惯。并查集初始化在调用Kruskal算法前一定要记得初始化并查集让每个节点的父亲都是自己。这个操作通常放在排序之后、遍历边之前进行。输入格式题目通常保证路口编号从1开始所以我们并查集数组也从1开始使用忽略下标0避免边界错误。3.2 Kruskal算法核心实现这是代码的核心部分实现了算法并同时获取两个答案。// 按照边的权值繁忙度从小到大排序 sort(edges, edges m, [](const Edge a, const Edge b) { return a.w b.w; }); // 初始化并查集 for (int i 1; i n; i) { father[i] i; } int edgeCount 0; // 记录已选中的边数 int maxWeight 0; // 记录当前选中的边中最大的权值即答案二 // 遍历所有排序后的边 for (int i 0; i m; i) { int fu find(edges[i].u); int fv find(edges[i].v); // 如果u和v不在同一个集合说明加入这条边不会形成环 if (fu ! fv) { unionSet(fu, fv); // 合并集合 edgeCount; // 选中边数1 maxWeight edges[i].w; // 更新最大边权 // 因为边是按权值从小到大遍历的所以当前加入的边权就是当前树中的最大边权 // 如果已经选中了n-1条边生成树构建完成 if (edgeCount n - 1) { break; } } } // 输出结果 cout n - 1 maxWeight endl;关键点解析排序使用sort函数和lambda表达式按边权w升序排列。这是Kruskal算法的第一步也是保证找到的是最小生成树的关键。并查集判环对于每条边检查其两个端点是否在同一个并查集集合中。如果不是则加入这条边不会形成环是安全的。答案更新edgeCount用于计数当它达到n-1时循环可以提前结束这是一个小的优化。maxWeight的更新是本题的精华。由于我们是按权值从小到大加边的因此每次成功加入的边其权值一定是当前已构成的部分生成树中最大的。当加入第n-1条边完成整棵树时maxWeight自然就是整棵树的最大边权即我们要求的“最小可能的最大繁忙度”。第一个答案题目明确要求输出最少道路数根据我们的推理就是n-1。直接输出即可甚至不需要通过算法计算。注意事项这里有一个初学者极易忽略的坑。题目只保证初始道路能使城市连通吗是的题目描述隐含了这个条件因为最终要求是“保持整个城市连通”。如果初始图就不连通那么不存在连通所有路口的方案也就不存在生成树。但竞赛题为了简化输入数据默认保证图是连通的。不过在更严谨的代码中可以在循环结束后检查edgeCount是否等于n-1。如果不等于说明图不连通但本题无需处理。3.3 完整代码参考将以上部分组合并添加一些基本的头文件就得到了本题的AC代码。#include iostream #include algorithm using namespace std; const int MAX_M 100005; struct Edge { int u, v, w; } edges[MAX_M]; int father[305]; int n, m; int find(int x) { return father[x] x ? x : father[x] find(father[x]); } void unionSet(int x, int y) { father[find(y)] find(x); } int main() { cin n m; for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } // 按边权排序 sort(edges, edges m, [](const Edge a, const Edge b) { return a.w b.w; }); // 初始化并查集 for (int i 1; i n; i) father[i] i; int cnt 0, ans 0; for (int i 0; i m; i) { int fu find(edges[i].u); int fv find(edges[i].v); if (fu ! fv) { unionSet(fu, fv); cnt; ans edges[i].w; // 更新最大边权 if (cnt n - 1) break; } } cout n - 1 ans endl; return 0; }4. 算法正确性证明与深入思考虽然代码写出来了但知其然更要知其所以然。为什么Kruskal算法求出的生成树其最大边权就是最小的这里提供一个简洁的证明思路有助于你真正掌握这类问题。反证法假设存在另一棵生成树T‘其最大边权W_max(T)小于我们通过Kruskal算法得到的生成树T的最大边权W_max(T)。设e是树T中权值为W_max(T)的那条边即最大的边。在T‘中由于T’也是一棵生成树连接了所有节点。如果我们把边e从T中移除T会被分成两个连通分量A和B。要想连接A和B在T‘中必然存在一条连接A和B的边e因为T’是连通的。根据Kruskal算法的执行过程它是按权值从小到大尝试加边的。边e之所以被加入T是因为在它被考虑时它是连接当时还未连通的两个分量的、权值最小的边。那么对于连接A和B的边e它在图中的权值w(e)一定大于等于w(e)。因为如果w(e) w(e)那么Kruskal算法在考虑e时它会在e之前被考虑就会发现它能连接A和B当时可能还不是A和B但一定是某两个未连通的部分并且不会形成环从而e会被选中而不是e。这与e是T中连接A和B的边矛盾。因此w(e) w(e) W_max(T)。这意味着在T‘中存在一条边e其权值至少为W_max(T)。所以T‘的最大边权W_max(T)也至少为W_max(T)。这与我们最初的假设W_max(T) W_max(T)矛盾。所以不存在最大边权更小的生成树Kruskal算法找到的生成树T就是“最小最大边权”生成树即最小生成树。这个证明过程也解释了为什么我们可以在Kruskal算法中用最后加入的边的权值作为答案算法保证每次加入的都是当前可选的、连接两个不同连通分量的最小权边因此最终构成树中最大的那条边其权值在所有生成树方案中是无法被更小的边替代的。5. 常见错误与调试技巧即使思路正确实现时也可能踩坑。下面是我在刷题和教学过程中总结的几个常见问题。5.1 数组越界这是最经典的错误。并查集数组开小题目说n 300但如果你习惯性地开father[305]在极端情况n300时循环for (int i1; in; i)是没问题的。但如果你不小心从i0开始初始化或者用了father[0]就可能出问题。安全起见可以开310。边数组开小题目给的是m的最大值比如5000。如果你定义edges[5005]输入循环用for (int i0; im; i)当m5000时i会从0遍历到4999刚好。但很多人会习惯性开edges[m]这在C里是变长数组虽然部分编译器支持但不是标准行为在洛谷等OJ上可能导致编译错误或运行时错误。最稳妥的方法是开一个足够大的固定数组如const int MAX_M 100005;。5.2 并查集实现错误并查集虽小但错一点全盘皆输。find函数忘记路径压缩写成return father[x] x ? x : find(father[x]);。这在数据量大时会导致超时。一定要写成father[x] find(father[x])再返回。unionSet函数合并错误常见的错误是father[fx] fy;或father[x] y;。正确的合并应该是将其中一个集合的根的父亲设置为另一个集合的根。即father[find(y)] find(x);或father[find(x)] find(y);。我代码中的写法father[find(y)] find(x);是将y所在集合的根挂到x所在集合的根下。没有初始化并查集在开始Kruskal循环前务必执行for (int i1; in; i) father[i] i;。忘记这一步所有find操作都会出错。5.3 答案输出错误第一个答案输出成cnt虽然cnt最终也等于n-1但题目要求的是“最少道路数”这是一个理论值。直接输出n-1更清晰也避免了万一图不连通虽然本题不会导致cnt不等于n-1而输出错误答案的风险。第二个答案更新时机错误maxWeight必须在成功加入一条边即fu ! fv成立时才更新。如果写在循环开头或if判断之外就会记录下最后一条遍历的边的权值可能是错误的。5.4 输入处理与数据类型边权范围题目未明确说明边权繁忙度的范围但通常可能是整数。保险起见存储边权的变量如Edge.w和答案变量ans应使用int。如果题目暗示可能很大则用long long。输入效率对于大规模输入如 m 10000使用cin可能会比scanf慢。在竞赛中如果担心输入卡时间可以使用scanf或关闭cin的同步流ios::sync_with_stdio(false); cin.tie(0);。5.5 调试技巧当你的代码提交后得到Wrong Answer (WA) 时可以按以下步骤排查检查样例首先确保能通过题目给出的样例。如果样例不过问题通常很明显。自造小数据构造一个N3, M3的简单连通图手动算出最小生成树和最大边权与程序输出对比。打印中间过程在Kruskal循环中打印每条边的信息(u, v, w)以及执行合并操作前后的并查集状态。这能帮你确认算法是否按预期选择了正确的边。验证并查集单独写一个函数打印整个father数组看看合并操作是否正确。边界测试考虑N1的情况只有一个路口。此时不需要任何道路最小生成树边数为0最大边权题目通常保证N2但思考边界有助于理解算法。对于N1我们的程序会输出0 0cnt永远到不了n-1ans保持初始值0这通常是合理的但需要看题目具体定义。6. 算法变种与拓展思考“繁忙的都市”是最小生成树最基础的一种变种。理解它之后你可以轻松解决一系列类似问题。这里列举几个常见的拓展方向6.1 求“最小生成树中权值最大的边”这就是本题的原型。解题模板完全一样Kruskal算法输出最后加入的那条边的权值。6.2 求“最小生成树中权值最小的边”这看起来更简单。根据Kruskal算法第一条成功加入的边就是权值最小的边。因为边是按权值排序的第一条不会形成环的边就是全局权值最小的边它一定会出现在任意一棵最小生成树中。6.3 判断给定边是否可能在/一定在最小生成树中这是一类更深入的问题。是否可能在对于一条边e(u, v, w)如果我们将所有权重小于w的边都加入图中用并查集维护连通性此时检查u和v是否已经连通。如果已经连通说明存在一条由更小权边构成的路径连接了u和v那么边e就不可能出现在任何最小生成树中因为可以用那条更小的路径替代它。否则e是可能的。是否一定在如果边e是连接当前图某两个连通分量的唯一桥梁或者所有其他能连接这两个分量的边权值都严格大于w那么e一定在所有最小生成树中。一种判断方法是考虑所有权重小于等于w的边用它们构建图或并查集如果去掉边e后u和v就不连通了那么e就是必须的。6.4 次小生成树问题这是最小生成树的一个经典衍生问题求权值第二小的生成树。通常的解法是先求出最小生成树T然后枚举不在T中的边e(u,v,w)将它加入T中此时会形成一个环找到这个环上权值最大的边不能是e本身并删除它得到一棵新的生成树。所有这样得到的生成树中权值最小的就是次小生成树。这需要结合倍增(LCA)等算法来快速查询树上两点间路径的最大边权。6.5 “繁忙度”定义变化如果题目把“最大边权最小”改为“总权值和最小”那就变回标准的最小生成树问题。 如果改为“最小边权最大”即求一棵生成树使得树中最小的边权尽可能大“瓶颈”最大化这就是“最大生成树”问题只需将Kruskal算法的排序改为从大到小即可。从“繁忙的都市”这道题出发我们不仅学会了一个具体的解题模板更重要的是掌握了将实际问题抽象成图论模型以及利用最小生成树性质解决特定优化问题的思维方法。这种“转化”和“应用”的能力才是算法竞赛和解决实际工程问题的核心。下次再遇到类似“在连通的前提下优化某种极端值最大/最小”的问题不妨先想想它是不是一棵最小生成树。