最小生成树
1.朴素Primm~n^2稠密图
Part1:例题
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。
数据范围:
1≤n≤5001≤n≤500
1≤m≤1051≤m≤105
Part2:思路
结构: g[N][N]邻接矩阵存树(稠密图)
dist[N]存储的是某一个点到集合的距离(这个点到集合内部所有的点的边中长度最小的边)
(最小生成树中的集合指的是:已经连接在一起的树/连通块)
bool st[]数组标记是否已经在连通块内
模版:
初始化dist[]数组为+∞(0x3f3f3f3f)
for循环n次迭代
找到1️⃣不在集合中的,2️⃣到集合距离最小dist[i]min的点t
ans记录累加最短边dist[t]
标记st[t]=true(已经加入连通块中了)
用dist[t]更新其他的所有不在集合中的点——到集合的最短距离(因为t是新加入连通块的,所有只需要与dist[t]比较是否更新)
最后输出ans
==⚠️注意特殊情况:==
没有连通块:
因为第一次加入的是一个点,没有边,每次默认把第一个点放进去。for循环找具有最短边的点t结束后,如果dist[t]==INF并且i!=1(i!=1是因为找第一个点的时候所有的边都是INF很正常,第一个点特殊除外),说明剩余所有的点没有连向连通块的。所以没有连通图,直接return
if(i&&dist[t]==INF) return INF;
有自环——自环不可以加入最小生成树,不可以作为最小生成树的边
自环有可能会把自己的最小距离dist[t]更新
apl eg:自环长度为-10,即g[t][t]=-10 在用dist[t]更新剩余所有点时,会有可能把自己也更新了。 for(int j=0;j<n;j++) dist[t]=min(dist[t],g[t][j]); 自环更新时:dist[t]=min(dist[t],g[t][t]);如果自环值更小,就会把dist[t]更新成自环长度,相当于把自环加入了最小生成树,后面ans+=dist[t]统计树边的时候,就会产生错误
所以先统计最小生成树边之和,再更新最短距离
ans+=dist[t]; for(int j=0;j<n;j++) dist[t]=min(dist[t],g[t][j]);
与Dijkstra()区别最大的一个地方在于更新最短距离这里
Dijkstra:
for(int j=0;j<n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
是到终点的最短距离,有累加的
但是最小生成树是到集合的最短距离(到集合中所有点的最短距离)
for(int j=0;j<n;j++) dist[j]=min(dist[j],g[t][j]);
代码
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
if(i&&dist[t]==INF) return INF;
if(i) res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[t][j]);
}
return res;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int t=prim();
if(t==INF) puts("impossible");
else cout<<t<<endl;
return 0;
}
2.Kruskal算法
n~m稀疏图
Part1:例题
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤1051≤n≤105
1≤m≤2∗1051≤m≤2∗105
Part2:思路
结构:
不需要存图,只需要存储所有边的信息,所以不需要复杂的数据结构queue/邻接表······,只需要用结构体存储所有边的信息
struct{a,b,w}edge[]——存储所有边的信息
并查集
p[]存储树的根节点(集合编码)
find()函数判断是否在同一集合中
res记录最小生活生成树中所有树边的权重
cnt存当前的连通图已经存入了多少边(为了判断最小生成树是否存在cnt<n-1说明不联通)
模版:
1. 将所有边按照权重从小到大排列——O(mlogm)
2. 枚举每条边(边连接两个点a,b,权重为c) 如果a,b所在集合不连通,把这条边加入集合中
3. 因为要用并查集判断两个点是否在同一集合中,还要将两个点进行联通,所以用到并查集的所有操作
4. 结构体排序:内部操作符重载
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;
int n,m;
int p[N];
struct Edge
{
int a,b,w;
bool operator< (const Edge &W)const
{
return w<W.w;
}
}edge[M];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int Kruskal()
{
sort(edge,edge+m);
for(int i=1;i<=n;i++)
p[i]=i;
int cnt=0,res=0;
for(int i=0;i<m;i++)
{
int a=edge[i].a,b=edge[i].b,w=edge[i].w;
if(find(a)==find(b)) continue;
res+=w;
cnt++;
p[find(a)]=find(b);
}
if(cnt<n-1) return INF;
return res;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
int t=Kruskal();
if(t==INF) puts("impossible");
else cout<<t<<endl;
return 0;
}