ACM入门：Prim与Kruskal算法详解（图论与最小生成树）

ACM模板库是一份专门为ACM（即国际大学生程序设计竞赛）入门选手准备的文档，它着重介绍了图论在算法设计中的应用，特别是两个经典的最小生成树算法：Prim算法和Kruskal算法。这些算法在解决实际问题中具有重要意义，对于理解网络结构、优化路径选择和构建最小成本连接等问题至关重要。 首先，Prim算法是用于求解带权重的无向图的最小生成树的一个高效算法。该算法的特点是从一个起始顶点开始，逐步添加边并保持生成树的总权值最小。Prim算法采用优先队列（这里使用了`priority_queue`）进行操作，其核心步骤包括初始化`mincost`数组（表示每个顶点到已选集合的最小代价），标记节点是否被访问（`vis`数组），然后在每次循环中选取未访问且与当前集合连接的边中代价最小的一条。Prim算法的时间复杂度为O(ElogE)，其中E代表边的数量。 代码中，`llprim()`函数定义了Prim算法的具体实现，包括设置上限常量`constllinf`和最大顶点数`constintmaxn`，以及`Edge`结构体来存储边的信息。`vector<Edge>edge[maxn]`用于存储图的邻接表，`mincost`数组记录从起点到每个顶点的最小成本，`vis`数组表示节点是否被访问过。在`prim()`函数中，通过不断更新`mincost`和`ans`（最小生成树的总成本）值，直到队列为空。 接下来是Kruskal算法，它是另一种著名的最小生成树算法，它将所有边按权重排序，然后逐个加入到生成树中，但只有当添加新边不会形成环时才会接受。Kruskal算法同样适用于有向或无向图，并且在处理有重边的情况下也能正常工作。在这个模板库中，用`intN`表示顶点总数，`edge`结构体用于存储边的信息，`addedge()`函数用于添加新的边，`cmp()`函数则用于比较边的权重。`findFather()`函数用于查找节点的根节点，防止形成环。 这两个算法是ACM竞赛中常用的图论基础工具，理解它们的工作原理和代码实现对于提升编程能力和解决问题的能力非常有帮助。熟练掌握并能灵活运用Prim和Kruskal算法，能够帮助参赛者在比赛中取得优势，尤其是在处理网络优化和连通性问题时。