P3366 最小生成树

P3366 最小生成树

在通信基站管网布线、电力网架设以及交通枢纽规划等重大工程中,如何在保证所有节点相互连通的前提下,使铺设线路的总建设开销(边权之和)达到全局最小,是经典的最小生成树(Minimum Spanning Tree, MST)离散优化问题。洛谷 P3366「【模板】最小生成树」作为 CCF GESP 七级核心考点(图论建模、并查集连通性维护、贪心算法证明)与 CSP-S 基础图论分水岭题目,给出了标准无向带权图的最小生成树求解规范。对于包含 N≤5000N \le 5000 个顶点与 M≤2×105M \le 2 \times 10^5 条无向边的稀疏图,若采用 Prim 算法(O(N2)O(N^2) 或堆优化 O(Mlog⁡N)O(M \log N)),实现复杂度与边稠密依赖较高;而基于“避圈法”与贪心割性质(Cut Property)的 Kruskal 算法,通过将所有边按权值升序快速排序(O(Mlog⁡M)O(M \log M)),结合带路径压缩的**并查集(Disjoint Set Union, DSU)**以均摊接近 O(1)O(1) 的反阿克曼函数时间高效维护连通块,能够以优雅精炼的代码结构在数十毫秒内锁定最优解。同时,题目明确要求当图不连通时输出 orz,这就要求算法在遍历边集的同时动态统计成功加入生成树的边数计数器 cnt,唯有满足 cnt == N - 1(且兼顾 N=1N=1 单点边界)方可确认全图连通。题目洛谷官方难度评级为普及/提高-。

luogu-P3366 【模板】最小生成树

🔗 洛谷原题传送门:luogu-P3366 【模板】最小生成树

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。

输入格式

第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_i,表示有一条长度为 ZiZ_i 的无向边连接结点 Xi,YiX_i,Y_i。

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例 #1

样例输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

样例输出 #1

7

提示

数据规模:

对于 20%20\% 的数据,N≤5N\le 5,M≤20M\le 20。

对于 40%40\% 的数据,N≤50N\le 50,M≤2500M\le 2500。

对于 70%70\% 的数据,N≤500N\le 500,M≤104M\le 10^4。

对于 100%100\% 的数据:1≤N≤50001\le N\le 5000,1≤M≤2×1051\le M\le 2\times 10^5,1≤Zi≤1041\le Z_i \le 10^4。

样例解释:

所以最小生成树的总边权为 2+2+3=72+2+3=7。


题目深度剖析

1. 最小生成树(MST)的数学定义与图论性质

设无向连通带权图为 G=(V,E)G = (V, E),其中顶点集为 VV(节点数 ∣V∣=N|V| = N),边集为 EE(边数 ∣E∣=M|E| = M),边权函数为 w:E→Rw: E \to \mathbb{R}。

  • 生成树(Spanning Tree):图 GG 的一个无向无环极小子图 T=(V,ET)T = (V, E_T),包含图 GG 的全部 NN 个顶点,且边数恰好为 ∣ET∣=N−1|E_T| = N - 1。在该子图中,任意两点之间存在且仅存在一条简单路径。
  • 最小生成树(MST):在图 GG 的所有可能生成树中,边的权值总和最小的生成树: W(T)=∑e∈ETw(e)达到全局最小W(T) = \sum_{e \in E_T} w(e) \quad \text{达到全局最小}

在图论与算法竞赛中,求解最小生成树主要有两大经典贪心算法:Kruskal 算法与 Prim 算法。本题节点数 N≤5000N \le 5000,边数 M≤2×105M \le 2 \times 10^5,边数远小于完全图边数上限 N(N−1)2≈1.25×107\frac{N(N-1)}{2} \approx 1.25 \times 10^7,属于典型的稀疏图(Sparse Graph)。Kruskal 算法以边为中心进行贪心选取,在稀疏图场景下具备实现简单、常数极小且内存占用极低的卓越优势。

2. Kruskal 算法的贪心本质与割性质证明

Kruskal 算法采用避圈加边贪心策略(Cycle-free Greedy Strategy),其算法流程如下:

  1. 将图 GG 中的所有边按照边权由小到大进行全局升序排序;
  2. 初始时,图中的每个顶点自成一个独立的连通块;
  3. 从权值最小的边开始依次遍历所有边:
    • 若当前边连接的两个顶点已属于同一个连通分量,加入该边会构成环(Circle),违背树的无环定义,故直接跳过(避圈);
    • 若当前边连接的两个顶点分属不同连通分量,则该边必然是连接这两个连通块的最优跨越边,将该边纳入最小生成树集合,并将这两个连通分量合并;
  4. 当成功选出的边数累计达到 N−1N - 1 条时,生成树构建完毕,提前退出循环;若遍历完所有边后边数仍不足 N−1N - 1,说明原图不连通。

正确性证明(基于割性质 Cut Property):

  • 割(Cut)与轻边(Light Edge):将顶点集 VV 划分为两个非空不相交子集 (S,V∖S)(S, V \setminus S) 称为图的一个割。若一条边的一个端点在 SS 中,另一个端点在 V∖SV \setminus S 中,则称该边跨越了这个割。在所有跨越该割的边中,权重最小的边称为该割的“轻边”。
  • 割性质定理:对于图 GG 的任意割 (S,V∖S)(S, V \setminus S),其轻边必然包含在图 GG 的某棵最小生成树中。
  • Kruskal 的数学保证:当 Kruskal 算法考查边 e=(u,v)e = (u, v) 时,由于 uu 与 vv 此时分属两个不同连通块,我们取 SS 为顶点 uu 所在的连通块,V∖SV \setminus S 为其余所有顶点构成的集合。因为所有边均按升序扫描,边 ee 是当前算法所能遇到的跨越集合 SS 与外部的第一条可用边,即跨越该割的边中权值最小者(轻边)。根据割性质,ee 必然属于图的最小生成树。因此,局部最优贪心选择直接推导出全局最优解。

3. 并查集(DSU)的连通性维护与路径压缩优化

在判断两点是否处于同一连通块及合并两连通块时,若采用全图 DFS/BFS 染色,每次耗时 O(N)O(N),总时间复杂度将退化至 O(M⋅N)O(M \cdot N),会导致严重超时。为此必须引入**并查集(Disjoint Set Union, DSU)**数据结构:

  • 初始化:每个节点设立父指针指向自身:fa[i] = i。
  • 查找根节点与路径压缩(Path Compression): 在查找节点 xx 所属集合的根节点时,递归返回并将沿途经过的所有节点的父指针直接指向根节点:
    int find_root(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find_root(fa[x]);
    }
  • 合并集合:若 find_root(u) != find_root(v),只需令 fa[root_u] = root_v 即可在 O(1)O(1) 时间内完成两连通分量的原子合并。
  • 在应用路径压缩优化后,并查集单次操作的均摊时间复杂度为反阿克曼函数 α(N)≤4\alpha(N) \le 4,在实际运行中完全可视为常数 O(1)O(1)。

4. 算法复杂度剖析与运行指标

  • 时间复杂度:
    • 边集排序:利用 std::sort 对 MM 条边进行内省排序(Introsort),耗时为 O(Mlog⁡M)O(M \log M)。
    • 边集遍历与并查集操作:遍历 MM 条边,每条边执行常数次并查集查找与合并,耗时为 O(M⋅α(N))O(M \cdot \alpha(N))。
    • 总时间复杂度:严格为 O(Mlog⁡M)O(M \log M)。
    • 本题 M≤2×105M \le 2 \times 10^5,Mlog⁡2M≈2×105×18≈3.6×106M \log_2 M \approx 2 \times 10^5 \times 18 \approx 3.6 \times 10^6 次基本运算,在现代化 CPU 评测机上执行仅需 0.03∼0.05 s0.03 \sim 0.05 \text{ s},远远快于 1.00 s1.00 \text{ s} 的评测时限。
  • 空间复杂度:
    • 边集静态数组 edges 存储 MM 条边,占用内存约 200005×12 B≈2.4 MB200005 \times 12 \text{ B} \approx 2.4 \text{ MB};
    • 并查集数组 fa 占用内存约 5005×4 B≈20 KB5005 \times 4 \text{ B} \approx 20 \text{ KB};
    • 总空间复杂度:严格为 O(N+M)O(N + M),总内存占用小于 5 MB5 \text{ MB},极大低于 125.00 MB125.00 \text{ MB} 的限制。

样例逐步手推演算

以题目样例为例:N=4N = 4 个结点,M=5M = 5 条无向边。 边集原始输入:

  • 边 1: (1,2,2)(1, 2, 2)
  • 边 2: (1,3,2)(1, 3, 2)
  • 边 3: (1,4,3)(1, 4, 3)
  • 边 4: (2,3,4)(2, 3, 4)
  • 边 5: (3,4,3)(3, 4, 3)

第 1 步:按权值升序排序后的边集:

  1. (1,2,2)(1, 2, 2)
  2. (1,3,2)(1, 3, 2)
  3. (1,4,3)(1, 4, 3)
  4. (3,4,3)(3, 4, 3)
  5. (2,3,4)(2, 3, 4)

第 2 步:初始化并查集: fa[1]=1,fa[2]=2,fa[3]=3,fa[4]=4fa[1] = 1, fa[2] = 2, fa[3] = 3, fa[4] = 4。当前生成树边数 cnt=0cnt = 0,总权值 sum=0sum = 0。

第 3 步:Kruskal 逐步扫描处理:

步骤当前考察边 (u,v,w)(u, v, w)根节点查找结果连通状态判定决策与并查集合并累计总权值 sumsum累计边数 cntcnt
1(1,2,2)(1, 2, 2)root(1)=1,root(2)=2root(1)=1, root(2)=2不连通(1≠21 \neq 2)选取该边,合并集合 1→21 \to 20+2=20 + 2 = 21
2(1,3,2)(1, 3, 2)root(1)=2,root(3)=3root(1)=2, root(3)=3不连通(2≠32 \neq 3)选取该边,合并集合 2→32 \to 32+2=42 + 2 = 42
3(1,4,3)(1, 4, 3)root(1)=3,root(4)=4root(1)=3, root(4)=4不连通(3≠43 \neq 4)选取该边,合并集合 3→43 \to 44+3=74 + 3 = 73
-提前终止--cnt==N−1=3cnt == N - 1 = 3,满足终止条件73

算法成功选出 3 条边,总权值为 2+2+3=72 + 2 + 3 = 7。输出整数 7,手推过程与官方样例输出完全吻合。


易错点与边界防坑指南

  1. 【防坑 1】图的不连通性判定与 orz 判定 题目要求:“如果该图不连通,则输出 orz”。 判定全图连通的充要条件是在扫描结束或提前跳出时,成功加入生成树的边数恰好等于 N−1N - 1。 若全部边扫描完毕后 cnt < N - 1,说明全图存在至少两个相互孤立的连通块,无法生成覆盖所有顶点的树,必须准确输出 orz。
  2. 【防坑 2】自环与重边的天然容错处理 输入数据中可能存在两点间的多条重边以及自环:
    • 对于自环 (u,u,w)(u, u, w),find_root(u)==find_root(u)find\_root(u) == find\_root(u) 必然恒成立,会被并查集直接忽略;
    • 对于重边,排序后权值较小的一条会被优先处理并使两端点连通,后续权值较大的重边再次考查时发现两端点已在同一连通块,自动触发避圈跳过。Kruskal 对重边与自环天然免疫。
  3. 【防坑 3】并查集父节点数组的 1-based 索引范围 题目顶点编号为 1∼N1 \sim N。初始化并查集循环必须写为 for (int i = 1; i <= n; ++i) fa[i] = i;。切勿漏掉节点 NN 或错误地从 0 开始覆盖。
  4. 【防坑 4】总边权累加防溢出(采用 long long) 虽然题目数据范围中 N≤5000,Zi≤104N \le 5000, Z_i \le 10^4,理论最大总边权约为 (5000−1)×104≈5×107(5000 - 1) \times 10^4 \approx 5 \times 10^7(未超出 32 位有符号整型上限),但在工程规范与进阶图论中,总权值变量务必使用 long long total_weight = 0; 累加,杜绝隐式整型溢出风险。
  5. 【防坑 5】静态内存开辟防系统栈溢出与 C++11 规范 边数规模 M≤2×105M \le 2 \times 10^5,边集数组 Edge edges[MAXM] 与并查集数组 int fa[MAXN] 必须定义在全局静态存储区(BSS 段)。严禁在 main() 函数栈中开辟大数组,避免触发段错误(Segmentation Fault / RE)。

C++ 完整参考实现

/**
 * 题目: 【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3366 【模板】最小生成树
 * 题号: P3366
 * 归属: GESP七级 / CSP-S / 洛谷经典图论模板
 * 博客: https://www.coderli.com/gesp-7-luogu-p3366/
 * 标准: C++11 (严格遵循 CCF GESP 官方规范)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 最大顶点数与最大边数常量
// 题目给定 N <= 5000, M <= 200000
const int MAXN = 5005;
const int MAXM = 200005;

// 无向边结构体定义
struct Edge {
    int u; // 起始顶点编号
    int v; // 目标顶点编号
    int w; // 边权值
};

// 全局静态边集存储数组
Edge edges[MAXM];

// 并查集父节点索引数组
int fa[MAXN];

// 边的自定义排序规则比较函数:按边权由小到大升序排序
bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

// 并查集查找根节点函数(采用路径压缩优化)
int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    // 递归查找根节点并将沿途所有节点的父节点直接指向根节点
    return fa[x] = find_root(fa[x]);
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读入 m 条无向边的信息
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 初始化并查集:每个顶点初始各自为一个独立的连通集合
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }

    // 将所有无向边按边权升序进行快速排序
    sort(edges, edges + m, cmp);

    long long total_weight = 0; // 记录最小生成树的所有边权累加和
    int edge_count = 0;         // 记录成功加入最小生成树的边数

    // Kruskal 算法核心贪心避圈选择过程
    for (int i = 0; i < m; ++i) {
        int root_u = find_root(edges[i].u);
        int root_v = find_root(edges[i].v);

        // 若当前边连接的两个顶点不在同一连通块内,则选取该边
        if (root_u != root_v) {
            fa[root_u] = root_v;        // 合并两个连通分量
            total_weight += edges[i].w; // 累加边权
            edge_count++;               // 树边计数自增

            // 当选取的边数恰好达到 n - 1 条时,最小生成树构建完成,提前退出
            if (edge_count == n - 1) {
                break;
            }
        }
    }

    // 若成功选取的边数达到 n - 1 条,则图连通并输出总边权
    // 对于单点图 (n = 1),所需边数为 0,同样符合条件
    if (edge_count == n - 1) {
        cout << total_weight << endl;
    } else {
        // 否则说明图不连通,按题目要求输出 orz
        cout << "orz" << endl;
    }

    return 0;
}

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于