ACM竞赛经典算法：Prim与Kruskal最小生成树实现

"ACM程序集是一份关于ACM（国际大学生程序设计竞赛）中常见算法的集合，特别关注图论问题，如最小生成树的Prim算法和Kruskal算法的实现。" 在ACM/ICPC（国际大学生程序设计竞赛/国际计算竞赛）中，参赛者需要解决各种算法问题，其中包括图论问题。这份文档提供的程序集重点讲解了如何在C++中实现两种经典的最小生成树算法：Prim算法和Kruskal算法。 1. **最小生成树** - 在图论中，最小生成树（Minimum Spanning Tree, MST）是指一个无向加权图的边的子集，这个子集中的边连接了图中的所有顶点，且边的总权重尽可能小。最小生成树在很多实际应用中都有重要作用，例如在构建成本最低的网络、规划最优路径等场景。 2. **Prim算法** - Prim算法是一种贪心算法，用于寻找加权无向图的最小生成树。它从一个初始节点开始，逐步加入边，使得每次加入的边连接的是当前树与尚未包含的顶点中权重最小的边。在给出的代码中，首先初始化所有边的权重为正无穷大，然后读取输入的边及其权重，用一个二维数组`ad`存储图的邻接矩阵。`prim()`函数实现了Prim算法的具体步骤，包括初始化标记数组`visit`和距离数组`mark`，通过循环找到未访问过的顶点中与已访问顶点相连的权重最小的边，不断更新最小生成树的总权重。 3. **Kruskal算法** - Kruskal算法也是求最小生成树的一种方法，它按照边的权重升序排序，然后逐一考虑每条边，如果这条边连接的两个顶点不在同一棵树（即不形成环），则将其加入结果。代码中`kruskal()`函数会执行这个过程，首先对边进行排序，然后遍历排序后的边，使用并查集（union-find）数据结构来判断是否形成环，并更新最小生成树的总权重。 这两种算法各有特点，Prim算法更适合稠密图（边数接近于顶点数的平方），而Kruskal算法更适合稀疏图（边数远小于顶点数的平方）。在ACM竞赛中，理解并灵活运用这些算法是解决问题的关键。 在准备ACM竞赛时，选手需要熟练掌握这些基础算法，并能根据具体问题快速调整和优化代码，以便在有限的时间内解决尽可能多的问题。通过学习和实践这些经典算法，不仅可以提升编程技能，也能培养解决复杂问题的能力。