叠甲：没事干写一篇好玩，不喜勿喷，有问题欢迎指出，暂时已完结。
本文只讲KRUSKAL，我在VJUDGE拉了个比赛包含所有题目,A-R题为例题，S-Y为附加题。
前置知识：并查集，贪心，树的性质，请先行了解。
一、最小生成树的定义
> 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树．也即在图的边集中选择 𝑛−1𝑛 −1n−1条，将所有顶点连通。我们定义无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。
> FromFromFrom oi-wiki
二、KRUSKAL算法模板
Kruskal算法是一种贪心算法，非常好写，算法的思想是由边权从小到大遍历，只要两个节点还未联通，就把它们连上。维护连通性的问题，套用单次合并O(logn)O(\log n)O(logn) 或者 𝑂(α(𝑚))𝑂(\alpha(𝑚))O(α(m))的并查集即可。加上排序的O(mlogm)O(m\log m)O(mlogm)，Kruskal算法的总复杂度为O(mlogm+mlogn)O(m \log m + m \log n)O(mlogm+mlogn)。
贴上模板代码（即A题代码）
三、例题
B
这就是最大生成树的模板，排序规则改掉就行了。
C
跑WWW遍最小生成树，注意在输入时给每条边加一个第几周开放的参数，跑最小生成树时检测边的开放时间是否小于等于当前时间即可，这样就不用每周都排序了。
D
假设能使用kkk个卫星设备，就相当于让kkk个点直接连通，在最小生成树中，一定会用k−1k-1k−1条边。那么最优方案就一定是把原图中最长的k−1k-1k−1条边的边权取消，只需输出最小生成树中第kkk长的边即可。
E
题目要求我们最大化任意两个部落之间的距离的最小值，实际上这个最小值就是在不同部落的任意两个居住点的最近距离。不难想到在部落内部尽量连较短的边，不让更短的边放在不同部落之间。因为要分为kkk个部落，因此只需要n−kn-kn−k条有用的边（遍历到这条边时两节点还未被联通的边）即可，所以直接输出第n−k+1n-k+1n−k+1条有用边的长度即可。（就是连结两个部落的边中最短的）
F
构造为图论问题，快速幂预处理连边，没了。
G
在线算法不知道怎么办，考虑离线处理，把所有查询的边都放进去排序，跑最小生成树，跑的过程中如果是原本就有的边直接正常处理，如果是查询边，检测这条边是否有用（即两个点是否已联通），如果有用就把Yes放入答案，没有就放入No，注意查询之间相互独立，所以就算有用也千万不要加边。
H
直接连边O(n2)O(n^2)O(n2)指定炸，考虑删边，例如当xi≤xj≤xkx_i \leq x_j \leq x_kxi ≤xj ≤xk 时，只需要连接iii与jjj、jjj与kkk，而不需要连iii与kkk。那么我们按x,yx,yx,y分别排序后将相邻点连边即可。可以证明如果一条边是有效的，那么一定不会在按xxx排序和按yyy排序后都被鉴定为无效边。
I
就是求在不用第一条边的情况下，第一条边的两个点联通的最小边权。跑第2−m2-m2−m条边最小生成树过程中检测第一条边两个点的连通性即可，注意如果最终都无法联通,输出10910^9109。
J
首先买了第 III 样东西，再买第 JJJ样的情况显然可以看做一条边权为KI,JK_{I,J}KI,J 的边，那么直接买一样东西花费AAA元的情况怎么办呢？这时候就可以引入一个超级源点，即000号点，这样就可以把这种情况构造为一条从000联向任意一点的边权为AAA的边了。
K
和J题几乎一模一样，挖水井就是向超级源点建边，修筑水道就是普通连边。
L
不讲了，L≈\approx≈K，但是注意这是远古题目答案末尾一定要换行！！！我被这个坑了20分钟。
M
笑点解析：
感谢PPL友情出演
接近正解的错误方法PPL已经给我们介绍过了，就是建两个超级源点分别代表港口与机场，然后暴力跑Kruskal，但是这样有个问题：我们的目标不是让包括超级源点在内的所有点联通，只是1−n1-n1−n号点的联通，因此可能会出现无效连边（明明1−n1-n1−n号点已经联通了还非要去连接超级源点）。
那么怎么办呢？注意到超级源点可以用也可以不用，那么枚举这两个超级源点的使用情况跑4遍Kruskal即可，注意可以给每条边一个编号，说明它属于机场边，港口边还是道路边，这样就不需要每次枚举使用情况都排序了。
那么为什么J、K、L没有这个问题呢？因为J、K、L题都必须使用超级源点，但是这道题就不一样了。
N
先不考虑额外的MMM条边，只看如何最小化生成树的ax+aya_x+a_yax +ay 之和，显然最优方案是一个菊花图，即将所有边都直接连向axa_xax 最小的点。如果不考虑额外MMM条边时，一条边不在最小生成树内，那么再加入MMM条边后，也一定不需要考虑，所以只需要连上原始生成树的N−1N-1N−1条边和额外的MMM条边并跑Kruskal即可。
O
不讲了，O≈\approx≈K，建边的公式不同，改一下就行了。
P
看完前面的题，你会发现Road真不难
首先因为村庄数少，不难想到遍历所有村庄的修复状态跑2k2^k2k次最小生成树，时间复杂度O(2kmlogm)O(2^kmlogm)O(2kmlogm)，48pts48pts48pts，考虑优化。
根据N题的剪枝方法，在不考虑村庄的情况下不在最小生成树内的边，有了村庄就更不可能在最小生成树内了。那么就可以预处理跑一边Kruskal，将最小生成树内的边放入新的边集，可以大幅缩减边数(1.1×106→1.1×1051.1\times10^6\to1.1\times10^51.1×106→1.1×105)。
根据M题的方法对包含村庄边在内的所有边进行预编号和预排序，这样就不用排2k2^k2k次序了。
最终时间复杂度O(mlogm+2knklogn)O(mlogm+2^knklogn)O(mlogm+2knklogn)，也可以加上启发式合并O(mlogm+2knkα(n))O(mlogm+2^knk\alpha(n))O(mlogm+2knkα(n))。
Q
这道题需要用Kruskal重构树。具体来说和普通的Kruskal唯一有区别的一点是Kruskal重构树不是直接连边，而是创造一个虚拟节点（例如在这题就是载重限制），让两个点变成这个虚拟节点的左右儿子（后面其实就是拿虚拟点合并了，虚拟点中父亲的点权一定小于（经常是大于）儿子的点权）。这题我们是希望限重越大越好，所以是跑最大生成树。查询的时候就求两个查询点在重构树上的LCA（一般朴素倍增即可），输出这个虚拟点的权值即可,时间复杂度O(mlogm+(n+q)logn)O(mlogm+(n+q)logn)O(mlogm+(n+q)logn)。好了恭喜你学会了Kruskal重构树，赶紧去把巅峰赛#31T6秒了吧。
R
不讲了，R≈\approx≈Q，上题是最大生成树，这题是最小生成树，没了。
大家觉得我有必要写S-Y吗（实际上除了S我一道都不会）
