2021年SWPUACM暑假集训day3最小生成树算法

前言 视频链接

视频连接：https://www.bilibili.com/video/BV1wV411s7Pe

练习题单

SWPUOJ题单：http://acm.mangata.ltd/training/61d5783bc488fd0507f8214a

题目连接题目名https://acm.dingbacode.com/showproblem.php?pid=1863畅通工程https://acm.dingbacode.com/showproblem.php?pid=1875畅通工程再续https://acm.dingbacode.com/showproblem.php?pid=1879继续畅通工程https://www.luogu.com.cn/problem/P3366P3366 【模板】最小生成树https://www.luogu.com.cn/problem/P2872P2872 [USACO07DEC]Building Roads Shttps://www.luogu.com.cn/problem/P1195P1195 口袋的天空https://www.luogu.com.cn/problem/P1194P1194 买礼物https://www.luogu.com.cn/problem/P2121P2121 拆地毯https://www.luogu.com.cn/problem/P1396P1396 营救https://www.luogu.com.cn/problem/P1991P1991 无线通讯网https://www.luogu.com.cn/problem/P4047P4047 [JSOI2010]部落划分https://acm.dingbacode.com/showproblem.php?pid=1598find the most comfortable road 什么是最小生成树

在讲最小生成树之前，我们先回顾一下什么是生成树：对于无向图G和一棵树T来说，如果T是G的子图，则称T为G的树，如果T是G的生成子图，则称T是G的生成树。而最小生成树就是对于一个有权值的图来说最小权值和的图就是最小生成树(也就是边权和最小的连通图，且只有n-1条边，其实也就是一颗树)

Kruskal算法

该算法的基本思想是从小到大加入边，是个贪心算法。Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。

原理虽然简单，但是需要一种数据结构维护一个森林，不能使其成环，或者说是维护多个集合，然后每次合并两个元素或者集合，这很容易和昨天学习的并查集联系起来，我们可以用并查集很轻松的维护这个森林。

如果使用 O ( m l o g 2 m ) O ( m l o g ⁡ 2 m ) O(mlog_2m)O(mlog⁡_2m) O(mlog2​m)O(mlog⁡2​m) 的排序算法，并且使用 O ( m α ( m , n ) ) O ( m α ( m , n ) ) O(mα(m,n))O(mα(m,n)) O(mα(m,n))O(mα(m,n))或 O ( m l o g 2 n ) O ( m l o g 2 ⁡ n ) O(mlog_2n)O(mlog_2⁡n) O(mlog2​n)O(mlog2​⁡n) 的并查集，就可以得到时间复杂度为 O ( m l o g 2 m ) O ( m l o g ⁡ 2 m ) O(mlog_2m)O(mlog⁡_2m) O(mlog2​m)O(mlog⁡2​m)的 Kruskal 算法。

证明

为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n − 1 n−1 n−1条边，即形成了一棵树。

证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

基础：对于算法刚开始时，显然成立（最小生成树存在）。

归纳：假设某时刻成立，当前边集为 F，令 T 为这棵 MST，考虑下一条加入的边 e。

如果 e e e 属于 T T T，那么成立。

否则， T + e T+e T+e一定存在一个环，考虑这个环上不属于 F F F 的另一条边 f f f（一定只有一条）。

首先， f f f的权值一定不会比 e e e小，不然 f f f会在 e e e之前被选取。

然后， f f f的权值一定不会比 e 大，不然 T + e − f T+e−f T+e−f就是一棵比 T T T还优的生成树了。

所以， T + e − f T+e−f T+e−f包含了 F F F，并且也是一棵最小生成树，归纳成立。

代码实现

（以hdu1863为例）

#include
using namespace std;

const int N = 1e2+10;
int fa[N];
int m,n;
struct edge {
    int u,v,w;
    bool operator w