部分内容摘自 李煜东《算法进阶》（个人认为非常好的一本书）
个人比较蒻，讲得可能不太清楚，建议大家还是翻翻书，查查资料，找一些比较权威的说法。那么接下来就是蒟蒻自己的一些理解了
最小生成树，就是给你一个无向图，让你选一些边出来，然后让这些边形成的新的图保持连通且边权之和最小。这样来理解可能比较通俗易懂，其实这么看来，让一个图保持连通且权值最小，先不考虑权值，我们最少需要n-1条边让这个图保持连通，此时这就是一个树形结构（可能大概这就是为什么叫最小生成树的原因吧），但是注意最小生成树不能直接跑最短路
那么如何构造出这一颗最小生成树呢？涉及到两种算法，一个是Prim算法和Kruskal算法
Kruskal算法
时间复杂度为O（m log m）
Kruskal算法总是会去维护无向图中的最小生成森林。最初，森林由零条边构成，每个节点自己构成一棵树
在生成最小生成树的过程中，会在剩余的边中选一条边权最小的边加入到森林中，且保证这条边连接的两个点不属于同一集合（还没有被放在森林中）。这样的话，我们就可以用并查集来实现这一个过程，不会的并查集的可以去看一下我另一个博客（无耻宣传）
Kruskal算法详细流程：
1.并查集初始化，每一个节点自己构成一个集合
2.将所有边按边权从小到大排序，遍历所有边(x,y,z)
3.若x,y不属于同一集合，那么加入这一条边，并将x,y合并；否则continue
4.所有的边扫描完之后，最小生成树已经构成
struct edge{
int x,y,z;
}e[MAXN];
bool cmp(edge q,edge w){
return q.z<w.z;
} //存边和排序
int f[MAXN];
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void merge(int x,int y){
f[find(x)]=find(y);
}//并查集基本操作
···
···
for(register int i=1;i<=n;i++) f[i]=i; //并查集初始化
for(register int i=1;i<=m;i++){
e[i].x=u,e[i].y=v,e[i].z=w;
} //存边
sort(e+1,e+1+m,cmp); //排序
int now=0,ans=0; //now为建了多少边，ans为权值之和
for(register int i=1;i<=m;i++){
int u=find(e[i].x),v=find(e[i].y);
if(u==v) continue; //如果在一个集合中就continue
else{
merge(u,v);
now++;
ans+=e[i].z;
} //合并，边权累加，已连边数++
if(now==n-1) break; //已经连通就退出
}
Prim算法
时间复杂度为O(n^2)，堆优化之后为O(m log n)，但其实堆优化之后不如Kruskal方便，所以Prim在处理稠密图和完全图时更加优秀，但是Kruskal还是比较实用的
Prim算法总是维护最小生成树的一部分，最初，Prim算法只确定1号属于最小生成树。我们设已经确定属于最小生成树的节点集合为T，剩余的节点集合为S。我们找到两个端点x和y，分别属于T和S，且边权最小，将y从S中删去，并加入到集合T中
我们可以维护一个数组d：对于x ∈ S，d[x]表示节点x与集合T中的节点之间权值最小的边的权值。若x ∈ T，则d[x]就等于x被加入T时选出的最小边的权值
int a[MAXN][MAXN],d[MAXN],n,m,ans;
bool v[MAXN];
void prim(){
memset(d,0x3f,sizeof d);
memset(v,0,sizeof v);
d[1]=0; //将1加入进去
for(register int i=1;i<n;i++){
int x=0;
for(register int j=1;j<=n;j++){
if(!v[j]&&(x==0||d[j]<d[x])) x=j; //如果没有加进去过且权值最小
}
v[x]=1;
for(register int y=1;y<=n;y++){
if(!v[y]) d[y]=min(d[y],a[x][y]); //维护d数组
}
}
}
···
···
memset(a,0x3f,sizeof a);
for(register int i=1;i<=n;i++) a[i][i]=0;
for(register int i=1;i<=m;i++){
a[x][y]=a[y][x]=min(a[x][y],z);
}
prim(); //求最小生成树
for(register int i=2;i<=n;i++) ans+=d[i];
以上大概就是对两种算法的讲解了，(Prim)讲解得不太清楚，可能需要读者自己理解一下（是我太菜。。。）
模板题，自己做，完全没有思维难度
我们之后的省选是这种难度那多好。
这道题稍微那么不模板一点，为什么呢？因为它有x轴和y轴，所以我们的边数应该是(n^2)，所以加一些处理就好了，还是把代码放出来
#include <bits/stdc++.h>
using namespace std;
double maxn=-20050206.0;
int n,m,ans,tot,now,x[2000010],y[2000010],a[2000010],fa[2000010],flag[2000010];
struct node {
int x,y;
double v;
} e[2000010];
inline bool cmp(node xx,node yy) {
return xx.v<yy.v;
}
inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main() {
scanf("%d",&m);
for(register int i=1;i<=m;i++) {
scanf("%d",&a[i]);
}
scanf("%d",&n);
for(register int i=1;i<=n;i++) {
scanf("%d%d",&x[i],&y[i]);
}
memset(e,20040915,sizeof e);
for(register int i=1;i<=n;i++) {
fa[i]=i;
for(register int j=1;j<=n;j++) {
if(i==j) continue;
e[++tot].x=i;
e[tot].y=j;
e[tot].v=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
sort(e+1,e+1+tot,cmp);
for(register int i=1;i<=tot;i++) {
int b=find(e[i].x);
int c=find(e[i].y);
if(b!=c) {
fa[b]=c;
now++;
maxn=max(maxn,e[i].v);
}
if(now==n-1) break;
}
for(register int i=1;i<=m;i++) {
if(a[i]>=maxn) ans++;
}
printf("%d",ans);
return 0;
}
上面一道题的一点点变种，只是对于不符合条件的边直接丢旁边不管就行了
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e7+50;
int n,c;
int x[MAXN],y[MAXN];
struct node {
int x,y;
int z;
} e[MAXN];
bool cmp(node q,node w) {
return q.z<w.z;
}
int f[MAXN];
int find(int x) {
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void merge(int x,int y) {
f[find(x)]=find(y);
}
int main() {
scanf("%d%d",&n,&c);
for(register int i=1; i<=n; i++) scanf("%d%d",&x[i],&y[i]),f[i]=i;
int tot=0;
for(register int i=1; i<=n; i++) {
for(register int j=1; j<i; j++) {
int w=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
if(w<c) continue;
else e[++tot].x=i,e[tot].y=j,e[tot].z=w;
}
}
sort(e+1,e+1+tot,cmp);
int now=0,ans=0;
for(register int i=1; i<=tot; i++) {
int u=find(e[i].x),v=find(e[i].y);
if(u!=v) {
merge(u,v);
ans+=e[i].z;
now++;
}
if(now==n-1) break;
}
if(now==n-1) cout<<ans;
else cout<<-1;
return 0;
}
这个题很舒服啊，它是一个矩阵，所以它是一个对称的图形，我们的读入只需要读取其中的一半，而剩下的一半再读入就会出现重边的情况。再看这道题的话，记得比较优惠和原价谁更便宜（为什么优惠之后会更贵啊）
#include <bits/stdc++.h>
using namespace std;
int n,m,u,tot,now,ans,fa[500010],flag[500010];
struct node {
int x,y,v;
} e[500010];
inline bool cmp(node xx,node yy) {
return xx.v<yy.v;
}
inline int find(int x) {
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main() {
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++) {
fa[i]=i;
for(register int j=1;j<=m;j++) {
scanf("%d",&u);
if(u!=0&&j>i) {
e[++tot].x=i;
e[tot].y=j;
e[tot].v=u;
}
}
}
sort(e+1,e+1+tot,cmp);
for(register int i=1;i<=tot;i++) {
if(now==m-1) break;
int b=find(e[i].x);
int c=find(e[i].y);
if(b!=c) {
fa[b]=c;
now++;
ans+=min(e[i].v,n);
}
}
printf("%d",ans+n);
return 0;
}