P3366最小生成树模板题详解：Kruskal与Prim实现与边界处理

1. 先看懂题目信息P3366 究竟想让你做什么1.1 题面信息剥开之后只剩一件事洛谷P3366【模板】最小生成树大概是很多算法竞赛选手写的第一道带“模板”标签的图论题。页面上的题目信息非常干净给出一张无向图有N个点M条边每条边有一个长度或者说边权最终要求输出最小生成树的各边长度之和。N不超过5000M不超过200000输入顺序就是先给N和M然后给M行三元组表示一条边连接哪两个点、权值是多少。理解这类题目有一个很重要的心态不要被“模板”两个字吓到。它的意思是说出题人刻意砍掉了所有干扰信息不给你设计复杂背景不设置小聪明样的输出陷阱就是为了让你在这里把最小生成树的算法本身练到滚瓜烂熟。你可以把这道题理解成“算法动作的考场”而不是“阅读理解考场”。真正要考察的只有三个动作能否正确建模最小生成树、能否正确实现算法、能否处理图不连通这种边界情况。看到 N5000、M200000 这个范围实际上也是在传递一条信息常规复杂度的解法都在安全区内。比如 Kruskal 的 O(M log M) 可以轻松通过朴素 Prim 的 O(N^2) 也才2500万次操作量级堆优化 Prim 的 O((NM) log N) 更是绰绰有余。要是哪份题解写出 O(NM) 甚至 O(N^2 log N) 的复杂度在这个数据范围下反而是需要警惕的。数据规模往往暗示了出题人想让你采用哪种算法这是做题时最先应该养成的直觉。1.2 模板题的隐藏要求图不连通就输出 orz如果只是输出边权和这题就太单调了。P3366 在题面里埋了一个小小的边界条件如果该图不连通则输出 orz。这个 orz 看起来像彩蛋实际上是对“最小生成树是否存在”的一次考察。最小生成树的定义建立在树的基础上树就是连通且无环的图。一个有N个点的无向图如果本身不是连通的那就不可能存在一棵覆盖所有点的生成树自然也就没有最小生成树。判断方法很多但写成模板的时候要特别注意Kruskal 里维护一个变量 cnt记录成功合并的次数只有当 cnt 达到 N-1 时