ACM竞赛算法整理：Prim最小生成树实现

"p_ACM算法集锦.doc" 这篇文档主要涉及了两个经典的图论算法：Kruskal's（克鲁斯卡尔）最小生成树算法和Prim's（普里姆）最小生成树算法，它们都是在解决如何找到一个无向图中权值最小的边集合，使得这些边连接起来的树包含了图中的所有顶点。 Kruskal's算法的基本思想是按边的权重从小到大排序，然后依次尝试添加边，但避免形成环路。在代码中，`all_e`数组存储了所有边的信息，包括起始顶点`u`、结束顶点`v`和权重`w`。`uni`函数用于判断并集操作是否会导致环路，如果不会，则将两条边合并到同一个集合中。在主函数`main`中，首先读入测试用例数`t`，然后对每个测试用例，读入顶点数`n`和边的信息，对边进行排序，接着通过`uni`函数逐个尝试添加边，直到构建出包含`n-1`条边的生成树，最后输出最小生成树的总权重。 Prim's算法则是从一个顶点开始，逐步扩展生成树，每次选择与当前生成树连接且权值最小的边。在代码中，`set`数组用于记录每个顶点所在的集合，`g`矩阵用于存储边的权重，`str`用于暂时存储输入。在`make_set`函数中，初始化每个顶点为独立的集合。在主函数中，首先从一个任意顶点开始，然后在每一步中更新与已选顶点相连的边，直到所有顶点都被包含在生成树中。每次选择的边是未被加入树且权重最小的边，最后输出最小生成树的总权重。 这两个算法常用于图论竞赛（如ACM/ICPC）和实际问题中，如网络设计、资源分配等场景，它们都致力于找到连接所有顶点的最小成本路径。理解并熟练运用这些算法对于解决复杂优化问题至关重要。