【CSP-J系列】 最小生成树
2026-07-07 15:28:18
发布于：浙江
求精华?
大家都知道，CSP-J不考MST，那为啥要写呢？我问我自己
反正学了那写吧。
道例题放心食用，MST 常考的类型大概就这几种。
正题
前情提要：最小生成树的英文为 Minimum Spanning Tree ，本帖里我们叫它 MST ，且时间复杂度中的均为边数，均为顶点数。
大家听到“最小生成树”可能会觉得这个东西就是个树，是一种很难的算法，其实不然，它更像是一种连接图的每个顶点的“马路”，就类似于最短路算法。
先看一个图。
这个图中红色的部分就是最小生成树，你可以看到这个树连接了图的所有顶点，且是权重最小的一个树，所以我们把这种 在该图所有合法生成树中，所有边的权值总和最小的那一棵生成树，叫作最小生成树 ，当然，因为它是树，所以当然 不能出现环 ，与最短路算法不同的是，这个最小生成树不是一条路径，像上图，它可以不保证任意两点之间的路径是最短路径，光说不用不行，下面来看一道例题。
这是道板子，下面我会用 Kruskal 算法 来帮助你解决这题。
Kruskal算法的核心思想就是 加边 ，在这个算法中会先将边 按边权排序，每次选取一个目前权值最小且 不在最小生成树中 的边，连接它的左右端点并 判环 ，如果不会连成环就将这条边加入进我们的最小生成树，其实有点类似于贪心思想，每次的边权都小，最后生成的最小生成树的边权总和一定也是最小的。
时间复杂度 ，主要的瓶颈是排序。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace syh;
typedef long long ll;
const int maxn=5005;
int fa[maxn];//并查集，记录每个顶点的祖先（父节点）
struct edge
{
int u, v;
ll w;
bool operator<(const edge &b) const//重定义“<”运算符，不然在排序的时候会报错
{
return w<b.w;//比较边权大小
}
};
int find(int x)//查找祖先
{
if(fa[x]!=x) fa[x]=find(fa[x]);//路径压缩（找到根节点）
return fa[x];
}
void unite(int x,int y)
{
x=find(x);//找x的祖先
y=find(y);//找y的祖先
if(x!=y)//两个祖先不一样就合并
{
fa[y]=x;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<edge> e;//用于存图的边
int n, m;
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int x, y;
ll z;
cin>>x>>y>>z;
e.push_back({x,y,z});//存进去这条边
}
for(int i = 1;i<=n;i++) fa[i]=i;//初始化并查集
sort(e.begin(),e.end());//排序所有边
ll sum=0;
int cnt=0;
for(auto edg:e)//遍历每条边
{
int u=edg.u, v=edg.v;//找两个顶点
ll w=edg.w;//边权
if(find(u)!=find(v))//我们尝试合并
{
cnt++;
sum+=w;
unite(u,v);//可以就合并
if(cnt==n-1) break;//如果树已生成就提前结束
}
}
if(cnt==n-1) cout<<sum;//有树就输出边权和
else cout<<"orz";
}
这里的cnt==n-1可能大家会有点问题，为啥边数到了就结束了？我们可以把这个树看成一个线段，就是把树给拉直，那么结点数就是植树问题里的棵数，边数自然就是间隔数-1。
总结一下， Kruskal 算法的核心就是 加边 先排序边权，再找边判环，这样就可以用 Kruskal 算法实现 MST，由于它是 加边 ，所以这个算法适用于边数较少的 稀疏图 。
下面我们来看另一种算法，Prim 算法。
Prim 算法的核心思想是 加点 也就是找离当前最小生成树最近的点并加入最小生成树，最后按点逐步生成最小生成树， 它的时间复杂度是 （朴素实现不加堆优化）， 堆优化后的时间复杂度是 ，由于是 加点 ，所以它适合 稠密图。
还是这道题，我们尝试用 Prim 算法 实现。
注意到 ，如果开int g[5005][5005];的话内存会爆炸，所以我们使用朴素 Prim 加上邻接表实现。
#include <iostream>
#include <cstring>
#include <vector>
using namespace syh;
const int maxn=5005;
const int INF=0x3f3f3f3f;//设置一个“无穷大”
typedef long long ll;
int n, m;
vector<pair<int,int>> vp[maxn];//邻接表
int dis[maxn];//点i到我们最小生成树的边权
bool vis[maxn];//是否加入最小生成树
int prim()
{
memset(dis,0x3f,sizeof dis);//初始化距离都为无穷大
memset(vis,0,sizeof vis);//都没加入最小生成树
dis[1]=0;//起点离自己距离为0
int cnt=0;//加入的顶点数
ll sum=0;//边权之和
for(int i = 1;i<=n;i++)//一共要n个顶点加入最小生成树
{
int u=-1, minn=INF;//为接下来的打擂设置初值
//暴力遍历所有不在最小生成树中的点u
for(int j = 1;j<=n;j++)
{
if(!vis[j]&&dis[j]<minn)//不在最小生成树中且是现在的最小距离
{
minn=dis[j];//更新最小距离
u=j;//将准备加入的点更新为现在的
}
}
if(u==-1) break;//没有可以加入的点，直接结束
vis[u]=1;//将现在的点加入最小生成树
sum+=minn;//加进这个点的边权
cnt++;//加入最小生成树的点加一
//准备修改现在不在最小生成树里的点离树的距离
for(auto e:vp[u])
{
int v=e.first;
int w=e.second;
if(!vis[v]&&w<dis[v]) dis[v]=w;//如果有更短的距离就更新
}
}
if(cnt!=n) return -1;
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int x, y;
ll z;
cin>>x>>y>>z;
vp[x].emplace_back(y,z);//储存边权
vp[y].emplace_back(x,z);//储存边权
}
ll f=prim();//能不能生成最小生成树
if(f==-1) cout<<"orz";
else cout<<f;
}
现在可能有同学会问，怎么这次的 cnt 要等于 了？之前不是等于 嘛? 其实这两个算法一个看的是加进去的边（Kruskal），一个看的是加进去的点（Prim），所以两个cnt 在判断上是不一样的。
帖主菜菜，例题等做到好的了再更
P2330 [SCOI2005] 繁忙的都市，怎么像模版的简化版？
这道题用 Kruskal 算法 写，因为我 Prim 不太会，我们求最少的道路显然就是一个 MST 问题，道路就是 条，最大的分值其实就是最小生成树里权重最大的边，我们用一个 打擂就行。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace syh;
typedef long long ll;
const int maxn=305;
int n, m;
struct edge//按边权从大到小排序
{
int u, v;
ll w;
bool operator<(const edge &b) const//重定义"<"符号
{
return w<b.w;
}
};
vector<edge> e;//存所有的边
int fa[maxn];//存父节点
int find(int x)//查找根祖先
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void unite(int x, int y)//合并连通块，先找各自根祖先，不一样就合并（就是判环）
{
x=find(x);
y=find(y);
if(x!=y)//根节点不同就合并
{
fa[y]=x;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int u, v;
ll w;
cin>>u>>v>>w;
e.push_back({u,v,w});//存进边集合
}
for(int i = 1;i<=n;i++) fa[i]=i;//自己是自己的祖先
sort(e.begin(),e.end());//先选边权小的边
ll maxw=0;//打擂的初值
int cnt=0;//初始化边数
for(auto &edg:e)//遍历每条边
{
int u=edg.u, v=edg.v;
ll w=edg.w;
int vu=find(u), vv=find(v);//找根节点
if(vu!=vv)//根节点不同（不会出现环）
{
unite(vu,vv);//合并（加进最小生成树）
maxw=w;//更新最大值
cnt++;//边数加1
if(cnt==n-1) break;//已经全部联通了
}
}
cout<<n-1<<" "<<maxw;//路最少n-1条，分值最大的路就是边权最大的那条边
}
P1661 扩散 ，新颖的MST问题啊。
其实和改造道路的那题一样，就是就最小生成树里最长的那条边的权重是多少，我们先求曼哈顿距离算出两点相交的最小时间，再按这个时间的长短进行排序，最后每次发现一条边就更新最大时间并加边，判断是否成为联通块即可。
代码放的是 Kruskal 算法 ，因为我把Prim忘了。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace syh;
typedef long long ll;
const int maxn=55;
int fa[maxn], n, a[maxn], b[maxn];
struct edge
{
int u, v;
ll w;
bool operator<(const edge &b) const//重定义"<"符号用于排边权
{
return w<b.w;
}
};
vector<edge> e;
int find(int x)//找祖先
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void unite(int x,int y)//合并
{
x=find(x);
y=find(y);
if(x!=y) fa[y]=x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i = 1;i<=n;i++) fa[i]=i;//初始化并查集
for(int i = 1;i<=n;i++) cin>>a[i]>>b[i];
for(int i = 1;i<=n;i++)
{
for(int j = i+1;j<=n;j++)
{
ll dis=abs(a[i]-a[j])+abs(b[i]-b[j]);//求两个中心点的间隔长度
ll w=(dis+1)/2;//两点联通所需时间
e.push_back({i,j,w});
}
}
sort(e.begin(),e.end());//按边权排序
int cnt=0;//一开始都没连
ll ans=0;
for(auto &edg:e)
{
int u=edg.u, v=edg.v;
ll w=edg.w;
if(find(u)!=find(v))//可以合并
{
unite(u,v);//合并
cnt++;//加进一条新边
ans=w;//更新现在的答案
if(cnt==n-1) break;//如果已经形成了连通块就结束
}
}
cout<<ans;
}
这题最重要的就是通过曼哈顿距离求出边权，其他的就和那道改造道路的很像了，基本就是对模版的复习。
这道题很 MST ，但是又有些不太一样，我们的问题是求最短的跨部落边，所以很显然要排边权，用 Kruskal 写，但因为要用最优划分，所以部落与部落之间的边绝对是边权较小的，在k个部落被划分完后，剩下的 条边中的第一条就是我们要找的答案，因为边权已经排好序了。
江苏省选强强，切绿还是难啊，转战黄绿青要失败了嘛。
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace syh;
const int maxn=1005;
int fa[maxn], n, k;//并查集
struct point//点的平面坐标
{
int x, y;
}p[maxn];
struct edge//存边
{
int u, v;
double w;
bool operator<(const edge &b) const
{
return w<b.w;
}
};
vector<edge> e;
int find(int x)//路径压缩
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void unite(int x,int y)//合并两个集合
{
x=find(x);
y=find(y);
if(x!=y) fa[y]=x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>k;
for(int i = 1;i<=n;i++) fa[i]=i;
for(int i = 1;i<=n;i++) cin>>p[i].x>>p[i].y;
for(int i = 1;i<=n;i++)
{
for(int j = i+1;j<=n;j++)//避免重复建边
{
//long long防止坐标平方溢出
long long dx=p[i].x-p[j].x;
long long dy=p[i].y-p[j].y;
double dis=sqrt(dx*dx+dy*dy);//计算欧几里得距离
e.push_back({i,j,dis});
}
}
sort(e.begin(),e.end());
int dot=n;//总点数
double ans=0;//最终答案
for(auto &edg:e)//从小到大遍历每条边
{
int u=edg.u, v=edg.v;
double w=edg.w;
if(find(u)!=find(v))//查找祖先，不同的就合并起来
{
if(dot==k)//如果已经是k个部落了那么此时的边权就是答案
{
ans=w;
break;
}
unite(u,v);//合并起来
dot--;//部落被合并了所以要减一
}
}
cout<<fixed<<setprecision(2)<<ans;//保留小数输出
}
注释较少因为一些函数的作用前面已经写过了，基本这种 MST 题就是套模版，但题会把边权的计算方式改一下，所以计算出边权 ，你离 就不远了。
P2121 拆地毯，最大生成树？
它可能真的是最大生成树，思想与最小生成树一样，反正都是求生成树，把重定义的"<"符号改成">"不就行了？但是sort排的时候需要写上greater<edge>()，不然会报错哦（edge是存边的结构体名字）。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace syh;
const int maxn=100005;
int fa[maxn];
int n, m, k;
struct edge
{
int u, v, w;
bool operator>(const edge &b) const//把"<"的定义改成">"就行啦
{
return w>b.w;
}
};
vector<edge> e;
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y) fa[y]=x;
}
int main()
{
cin>>n>>m>>k;
for(int i = 1;i<=n;i++) fa[i]=i;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
e.push_back({u,v,w});
}
sort(e.begin(),e.end(),greater<edge>());//没有后面的从大到小排会报错
int cnt=0, ans=0;
for(auto &edg:e)
{
int u=edg.u, v=edg.v, w=edg.w;
if(find(u)!=find(v))
{
unite(u,v);
ans+=w;
cnt++;
if(cnt==k) break;
}
}
cout<<ans;
}
其实过程都是一样的捏。
P1396 营救 写上瘾了，这个最后一题吧。
一道最小瓶颈路。我们把 MST 模版打一遍，再在每次合并的时候判断一下现在两个区到底有没有联通就行，因为边是按拥挤度排的，所以最后的那条边（最后遍历到的）就是我们要的答案。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace syh;
const int maxn=9168;//别问我为什么开9168都能过因为我试了好多次这个的最低限制
int fa[maxn], n, m, s, t;
struct edge
{
int u, v, w;
bool operator<(const edge &b) const
{
return w<b.w;
}
};
vector<edge> e;
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y) fa[y]=x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>s>>t;
for(int i = 1;i<=n;i++) fa[i]=i;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
e.push_back({u,v,w});
}
sort(e.begin(),e.end());
int ans=0;
for(auto &edg:e)
{
int u=edg.u, v=edg.v, w=edg.w;
if(find(u)!=find(v))
{
unite(u,v);
if(find(s)==find(t))//合并后s区是否与t区相连
{
ans=w;//相连那么答案就是此时的拥挤度，因为边是按拥挤度大小排序的
break;
}
}
}
cout<<ans;
}
大家还是开 好哦，我只是想看看题目数据好不好所以才去试的（战绩可查），比赛可别在这里 RE。
总结一下，实现最小生成树的算法通常有 种，分别是 Kruskal 算法（边优先） 和 Prim 算法（点优先），前者适用于 稀疏图 ，后者适用于 稠密图 ，两者时间复杂度相近，都可用堆优化，但它们都只可适用于 无向连通带权图 ，Kruskal 算法要判断是否形成环，而Prim只需每次加进离现在最小生成树最近的点即可。
有帮助，赞一个