最小树形图构建与自环处理算法详解

最小树形图是一种图论中的概念，它指的是在有向图中找到一棵具有最少总权重的树，其中每个节点都恰好有一条指向根节点的边。在实际应用中，比如在HDOJ题目HDU4009 Transferwater中，这种结构被用于解决供水问题，通过构建最小代价的连接网络，使得非水源地区的居民可以以最低成本获取水源。 在实现最小树形图的过程中，首先需要对输入的有向图进行预处理，移除所有自环，因为自环不会出现在树形结构中，这样做是为了确保算法的时间复杂度为O(VE)，其中V是节点数，E是边数。接下来的算法步骤如下： 1. 初始化：将所有节点的入边权重设为无穷大（`in[i]=inf`），并记录每个节点的前驱节点（`pre[v]`）。如果找到一个节点u与v之间的边，且权重小于v当前的入边权重，那么更新v的入边权重和前驱节点（`in[v]=node[i].w` 和 `pre[v]=u`）。 2. 遍历查找：对于每个节点i，检查其入边权重，如果发现某个节点（非根节点）的入边权重为无穷大，表示该节点孤立，这时返回-1，表明图中存在不能构成树形图的结构。 3. 标记环：对每个节点进行深度优先搜索（DFS），标记出是否存在环。如果遇到环，将其转换为一个虚拟节点（`id[u]=cntnode`），同时更新计数器`cntnode`。如果遍历结束时没有发现环，则说明当前图已经是最小树形图，可以跳出循环。 4. 重新标记非环节点：将剩余未标记的节点作为新图中的新节点（`id[i]=cntnode++`）。 5. 更新边信息：根据新图的节点编号，更新原有边的起点和终点，以及边的权重（如果边的方向不变，权重减去原入边权重，否则保持不变）。 6. 结果处理：最后，调整节点数和根节点的编号，以便适应新的图结构。 通过以上步骤，我们可以找到一个最小树形图，它代表了最经济高效的供水方案。这种方法不仅适用于HDOJ中的特定问题，也广泛应用于网络优化、资源分配等场景中，体现了图论在实际问题中的强大应用价值。