生成树的定义：是指在一个带权的无向联通图中选择$n$个点和$n-1$条边构成的无向联通子图。
最小生成树的定义即为边权最小的生成树。
求最小生成树最常用的两种算法为：Prim和Kruskal。Prim常用于稠密图，Kruskal则相反。
Prim算法的思路与Dijkstra算法非常相似。定义$S$为当前已经确定了属于最小生成树的结点，$T$为集合外的结点。使用dist数组存储每个结点到$S$集合的距离，距离定义为如果有多个结点指向$S$集合，则距离最短的边为这个结点到$S$集合的距离。最开始初始化所有结点到$S$集合的距离为$+\infty$，$1$号点到$S$集合的距离为$0$。一共进行$n$次迭代，每次找到$T$集合中距离$S$集合距离最短的结点$t$，然后用$t$结点更新其他点（与$t$相连的结点）到$S$集合的距离，然后把$t$从$T$集合中删去，加入到$S$集合中，则$t$结点为当前已经确定了属于最小生成树的结点。
具体的做法是用一个布尔数组来标记一个点是否属于$S$集合，st[i]为true则结点$i$属于$S$集合，反之不属于。每次从未标记的结点中选择一个dist值最小的结点，把这个结点加入到$S$集合中，并把这个结点的权值加到答案里，然后更新所有出边。
使用数学归纳法证明：
证明对于$\forallk
初始$k=1$，存在一棵最小生成树数包含第一步选择的最短的边，证明显然成立。
假设算法前$k$步选择的边能包含在最小生成树中，那么第$k+1$步选择的边也包含在最小生成树中。
第$k+1$步算法选择的边为$e_{k+1}$，并且权值最小。同样用反证法证明，假设没有选择$e_{k+1}$这条边，选择了另一条$e_{k+1}'$这条边，如果把$e_{k+1}$选择上，会构成一条回路，但如果把$e_{k+1}'$删去，构成了一棵树，并且总权值之和不会变大。
所以算法第$k+1$步仍可得到最小生成树.
constintN=510,M=1e5+10,INF=0x3f3f3f3f;intn,m,dist[M],st[M],g[N][N];//g数组用邻接矩阵存储图intprim(){memset(dist,0x3f,sizeofdist);dist[1]=0;intres=0;for(inti=0;i intn,m,p[N];structNode{inta,b,c;}e[M];intfind(intx)//并查集{p[x]=p[x]!=xfind(p[x]):p[x];}intkruskal(){sort(e,e+m,[&](Node&a,Node&b){//将每条边的权值从小到大排序，这里使用了Lambdareturna.c