最小生成树一篇通（未完成）
2026-05-07 22:44:01
发布于：上海
本质上似乎都是贪心。毕竟叫最小生成树了。
1.Prim
用一个dis数组来记录到目前为止当前树中的点到其他点的最短边长。
先将一个随机的点（这里选择一号点）放入生成树，遍历它的边。
用它的边来更新dis。标记它。
这里用一个结论：任何时刻未标记的点中dis最小者，其dis值所对应的边一定在一颗最小生成树中。
把所有未标记点中dis最小的那个点标记，遍历它的边。
重复上述操作。
时间复杂度O(n^2+m)。
注意到这个过程其实很想dijkstra。所以不难想到它可以用优先队列优化。
时间复杂度O(mlogn).
题目：最小生成树-模板
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
vector<Node>v[N];
int dis[N];
bool vis[N];
typedef long long ll;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,zz;
cin>>x>>y>>zz;
v[x].push_back({y,zz});
v[y].push_back({x,zz});
}
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
dis[1]=0;
pq.push({1,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
pq.push({to,dis[to]});
}
}
}
int sum=0;
ll ans=0;
for(int i=1;i<=n;i++){
if(dis[i]!=INT_MAX)sum++;
ans+=dis[i];
}
if(sum!=n)cout<<"orz";
else cout<<ans;
return 0;
}
注意：更新dis[i]需要确保vis[i]没有被标记。
2.kruskal
其实逻辑本身和prim是一样的。只是实现方式不同罢了。
kruskal：将所有边排序，根据边权从小到大遍历每条边。如果当前边连接的两个节点来自不同的连通块，那么就将这条边加入最小生成树。
插播小广告：并查集
想要写出kruskal，我们需要先学会并查集。
由于我早就修为散尽，所以我的并查集可能写的很烂，如果弄不懂的话可以直接看oi-wiki
并查集需要支持两个操作：1.合并（将两个元素所属集合合并） 2.查询（查询两个元素所属集合是否为同一个）
开始时，每个元素属于一个单独的集合。每个节点的父亲节点设为自己（使用一个f数组来存储当前节点的父亲节点）。
如何查询：当前节点为i，使得i=f[i]，直到i==f[i]。
考虑到集合内顺序并不重要，我们可以直接使得当前节点（i)的f[i]设置为根节点。（路径压缩）
合并：合并两棵树，只需要将一颗树的根节点改成另一棵树的根节点。
然后就可以开始挫代码了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int z[N];
int zu(int xxx){
return (xxx==z[xxx])?xxx:z[xxx]=zu(z[xxx]);
}
struct Node{
int x,y,z;
}v[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
typedef long long ll;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i].x>>v[i].y>>v[i].z;
}
sort(v+1,v+1+m,cmp);
ll ans=0;
int sum=1;
for(int i=1;i<=n;i++)z[i]=i;
for(int i=1;i<=m;i++){
int xx=v[i].x,yy=v[i].y;
if(zu(xx)!=zu(yy)){
ans+=v[i].z;
sum++;
z[zu(xx)]=z[zu(yy)];
}
}
if(sum!=n){
cout<<"orz";
return 0;
}
cout<<ans;
return 0;
}
并查集的每次操时间是一个极小的常数。
所以，kruskal的时间复杂度瓶颈在排序上。时间复杂度为O(mlogm)。
明天会弄一些例题。
例题：买礼物
先说做法，再说想法。
做法：有优惠，一件礼物作为一个顶点，价格为边。建立零点，将零点与其他每个顶点连边，代表原价购买此商品。
由于在熟悉，所以prim和kruskal都会拿出来弄一遍。
prim:
#include<bits/stdc++.h>
using namespace std;
//prim
const int N=5e2+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[N];
priority_queue<Node>pq;
int dis[N];
bool vis[N];
int main(){
int a,b;
cin>>a>>b;
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int x;
cin>>x;
if(x==0)continue;
v[i].push_back({j,x});
}
}
for(int i=1;i<=b;i++){
v[0].push_back({i,a});
v[i].push_back({0,a});
}
for(int i=0;i<=b;i++)dis[i]=INT_MAX;
dis[0]=0;
pq.push({0,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
pq.push({to,dis[to]});
}
}
}
int ans=0;
for(int i=1;i<=b;i++)ans+=dis[i];
cout<<ans;
return 0;
}
在写prim的时候，我发现了一点比较有意思的事情。
我将vis[k]=1改动成了：
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
vis[to]=1;
pq.push({to,dis[to]});
}
}
如果加在了这里，那么如果后续我还能用别的边来优化dis，就优化不到了。
当时居然没注意，随意改了一下酿成大错qwq。
接下来是kruskal的版本。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
struct Node{
int x,y,z;
}node[N];
int c[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int f(int x){
return (x==c[x])?x:c[x]=f(c[x]);
}
typedef long long ll;
int main(){
int a,b;
cin>>a>>b;
int n=0;//总共有多少条边
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int xx;
cin>>xx;
if(xx==0)continue;
node[++n]={i,j,xx};
}
}
for(int i=1;i<=b;i++)node[++n]={0,i,a};
sort(node+1,node+1+n,cmp);
for(int i=0;i<=b;i++)c[i]=i;
ll ans=0;
for(int i=1;i<=n;i++){
int xx=node[i].x,yy=node[i].y;
if(f(xx)!=f(yy)){
ans+=node[i].z;
c[f(xx)]=f(yy);
}
}
cout<<ans;
return 0;
}
分析：
1.如何分析这道题目需要用到最小生成树
分析这个问题，先需要想到，这是一道和图论相关的问题。
如何将一个实际问题转化成为图。或者说如何识别有“图”。
它有点之间的关系。点i和点j之间的联系就是k[i][j]。
那么这个联系就可以变成边。
想在图论相关的题目中找”最小“。那么一般考虑：最短路，最小生成树，树形dp(我对树形dp不太了解，但应该也是相关）。
然后再看，这道题目需要求取整个图的所有边权。比较容易想到最小生成树。
最后分析复杂度：一共有n*n条边。大约2e5。可以支撑的起O(mlogn)的时间复杂度。
2.使用prim更好还是使用kruskal更好。
稠密图。推荐使用prim。
好的，来看下一道例题：构造树
题目大意：一颗有n个结点的树，其中每条边有一个正整数边权。但并不知道这颗树的样子，只知道每两点之间最短路长度，但是这些最短路长度可能是错误的。请判断是否存在一颗树满足条件。
样例
输入：
3
0 2 7
2 0 9
7 9 0
输出：
YES
先说做法，再分析。
我们先将图根据题目所给出的信息建出来。
如果这n个点能构成一颗符合条件的树（指符合题目要求的树），那么一定是该图的生成树。
回顾kruskal算法的过程。一条点u到v，边权为w的边属于最小生成树，那么就代表其他所有边权小于w的边没能使得点u和点v连通。（这边的最小生成树指的是我们用图中的边建立的最小生成树）
这也就意味着在最后的生成树中（也就是我们在图中建立的生成树）这两点的路径一定会经过至少一条边权大于等于w的树。
这样下来，这两点之间的距离一定会大于等于w。只有在点u和点v直接相连的时候才能取到相等。
而点u和点v之间只会有一条边。边权是两点之间的最短距离。
因此只有在这颗树是最小生成树的时候，它才可能是满足条件的树。
这一通分析后，各位大概率还是一知半解。不过后续会进行更详细的分析。
有帮助，赞一个