ACM算法详解：构建最小生成树

"这是一份关于ACM（国际大学生程序设计竞赛）中常用的算法集合，包含了图论中的最小生成树算法。" 在ACM算法集中，经常会遇到各种类型的算法问题，其中图论算法是重要的组成部分。这段代码展示了一个用于求解最小生成树的问题，采用了Prim算法或Kruskal算法的一种变体。最小生成树问题是在一个带权重的无向图中找到一个边的集合，使得这些边连接了图中的所有顶点，并且这个集合的总权重尽可能小。 代码首先定义了一个结构体`edg`，用于存储图中的边，包含两个顶点`u`和`v`以及边的权重`w`。`#define`宏定义了一些常量，如边的最大数量`M*M/2`和一个较大的整数值`LIM20000000`。 接着，代码实现了一个名为`uni`的函数，该函数用于合并两个集合（通过数组`set[]`表示），并返回是否成功合并成一个更大的集合。这是并查集数据结构的一个简化版本，用于处理无环连接问题。 在`main`函数中，首先读取测试用例的数量`t`，然后对每个测试用例进行处理。首先清空`set[]`数组，然后读取图的节点数`n`，接着读取每对节点之间的边及其权重。所有边按照权重排序，以便在寻找最小生成树时能优先考虑权重较小的边。 接下来的循环中，使用`uni`函数尝试将每条边加入到当前的最小生成树中，同时保持图的连通性。每次成功合并两个集合时，`count`计数器加一，如果新添加的边权重大于当前已找到的最小边权重，则更新这个最小值。当连接的节点数达到`n-1`时，最小生成树构建完成。 最后，输出最小生成树的总权重，即边`all_e[max]`的权重，代表了整个图的最小生成树的总成本。整个程序的运行结束。 这段代码提供了一种解决最小生成树问题的方法，对于ACM竞赛或图论算法的学习者来说，这是一个实用的例子。它展示了如何在实际编程中应用并查集和排序等基本算法技巧来解决问题。