定义：

生成树：无向图包含所有点的生成子图（即边集包含于原图），且是一棵树。

最小生成树：边权和最小的生成树。

基本性质：

如果把边权看做代价，那么最小生成树就是使全图连通的最小代价。

最小生成树同时满足整棵生成树上的最大边权最小，任意两点间的最大边权最小（这个性质由kruskal算法的执行过程即可得出）

算法：

Prim算法

适合处理稠密图，算法复杂度$O(n^2)$

kruskal算法

适合处理稀疏图，算法复杂度$O(m\log m)$。

另外堆优化Prim（和堆优化dijkstra写法差不多）算法复杂度可降至$O(m\log n)$，但无太大实际用途。

例题1：[FAIOJ1347]繁忙的都市

题意：求最大边权最小的生成树。

直接用板子就行了。。。

例题2：[NOIP2013][luogu1967][FAIOJ10132]货车运输

题意：求两点间最小边权最大的路径，所以是最大生成树。

用kruskal算法求出最大生成树，然后问题就变成$q$次询问树上两点间最小边权。

本题数据范围很小，暴力$DFS$或倍增均可。复杂度$O(qn)$（暴力）或$O(q\log n)$（倍增）

例题3：[FAIOJ1934]安慰奶牛

题意：给一张无向图，求一棵生成树，使得从一个顶点遍历完整棵生成树再回到原点经过的点权和边权之和最小。

首先不难看出，从一棵顶点遍历整棵树再回到原点，会恰好经过所有的边两次。

每经过一条边，都会同时经过其连接的两个顶点。

但因为经过相邻的两条边会重复经过其重合顶点，所以不能简单地将点权加到边权上。

可以理解为经过一条边的同时经过其连接的顶点“半次”。

这样把每条边$(u,v)$的边权改为$W_u+W_v+2\times W(u,v)$做最小生成树即可。

复杂度$O(m\log n)$。

例题4：[FAIOJ30066]新的开始

我们新建一个虚点$S$。

如果一个点上有发电站，就把$S$和这个点连边。

这样，和$S$连通的点就都是有电力供应的。

因此相当于求使全图连通的最小代价。加边$W(S,u)=v$后Prim即可。

复杂度$O(n^2)$

例题5：[FAIOJ30067]构造完全图

首先观察新加的边要满足什么性质。

对于一条边$(x,y)$，要使原树$T$为最小生成树，必须有$W(x,y)>W(u,v)$，其中边$(u,v)$在$T$上$x$到$y$的路径上。

因为要求边权和最小，所以直接让它等于$\max W(u,v)+1$即可。

因此按边权从小到大依次加入并使用并查集维护。

每次合并$u,v$所在的两个连通块时，它们满足：块内的边边权都$\le W(u,v)$

因此两块之间的最大边就是$W(u,v)$。故$W(u,v)+1$在完全图中出现了$s{z}_u\times s{z}_v-1$次。

复杂度$O(n\log n)$。