ACM经典算法集：构建最小生成树与并查集应用

本文档是一份针对ACM（美国计算机协会）竞赛中的常用算法集合，特别是关于图算法部分。作者提供了一个名为Kruskal's Minimal Spanning Tree（克鲁斯卡尔最小生成树）的实现代码模板，这是解决图论问题中经典的一种方法。 Kruskal's算法是一种用于寻找无向加权图中最小生成树的贪心算法。在这个模板中，代码定义了一个`edg`结构体来表示图中的边，包括起始顶点`u`、结束顶点`v`和边的权重`w`。`operator<`函数用于在排序边时按照权重进行比较，确保在构建最小生成树时总是选择当前权重最小的边。 在`uni`函数中，作者实现了并查集数据结构，用于跟踪连通分量。该函数接收两个集合的代表元素，通过路径压缩和合并操作将它们合并到同一个集合中，并判断是否形成环路。这个函数对于Kruskal算法至关重要，因为它需要频繁地合并节点来构建树形结构。 `main`函数部分展示了如何处理输入的测试用例。首先读取测试案例的数量`t`，然后循环遍历每一个案例，对每一条边进行处理。首先清空并查集，接着读取图的节点数量`n`和边的信息，通过嵌套循环获取所有边，并根据边的权重对它们进行排序。接下来，通过`uni`函数逐步添加边到最小生成树，直到达到`n-1`个连通节点。在添加过程中，记录最大权重的边，即生成树的总权重。 最后，输出最大权重值，即最小生成树的总成本。整个代码模板提供了一个简洁而高效的实现，适用于ACM竞赛中需要求解最小生成树问题的情景。 总结起来，这份文档的核心知识点包括： 1. **Kruskal算法**：一种用于找到无向加权图最小生成树的贪心算法。 2. **图数据结构**：`edg`结构体表示边，包含起始点、终点和权重。 3. **并查集**：`uni`函数实现并查集数据结构，用于维护图中的连通性。 4. **排序与贪心选择**：利用`sort`函数和自定义比较运算符`<`进行边的优先级排序。 5. **算法流程**：读取输入、构建并查集、添加边到最小生成树、计算并输出最小生成树的总权重。 通过理解和掌握这些核心知识点，参赛者可以有效地解决涉及图论的ACM题目。