建站
咨询
售后
建站咨询
最小生成树Kruscal算法（C++）-创新互联
求点赞，求关注，小UP想变大UP的梦想就靠你实现了！
新闻名称：最小生成树Kruscal算法（C++）-创新互联
文章网址：http://scgulin.cn/article/ihgde.html
最近新入了一个画图软件，讲讲图论再合适不过了
我们来看这样一个东西
找到一棵树，边长之和最小，也就是最小生成树
一个一个选DFS，太慢了
那怎么办呢？
Kruscal我们注意到，边长之和最小
那我们优先选边长之和最小就可以了呀
但要选的是一棵树，如果按这个想法，可能会有回路产生，那就不好了
我们之前讲了并查集
想一下，可以用并查集吗
我们看两个点的最老的祖先节点，如果两个是同一个点，就不能选了
我们的想法就好了
设每一条边是x-y，长度为k，我们按照k排序，如果两个点x,y的最老的祖先节点一样，那这条边就不添加
我们来模拟一下样例
选中的边红色，不能连的黄色，剩下最小的绿色，没连的蓝色
当你连了点数N-1条边，就是一颗最小生成树
图例1
最终的最小生成树（这个图不太好，没有黄色的边出现）
再来一个
图例2
并查集告诉我们AC不能连
至此，最小生成树产生了
原理讲完了，我们看题
例1登录 - 沐枫OJ
https://www.mfstem.org/p/688可以说模板题，没啥好讲的，代码里有注释讲解，自己看吧
#includeusing namespace std;
#define int long long
int n,tp,f[10005],sum,ans;
struct road{//定义x,y,t
int x;
int y;
int t;
}r[100005];
bool cmp(road a,road b){//排序
return a.t< b.t;
}
int fi(int x){
return f[x] == x ? x : f[x] = fi(f[x]);//找最老的祖先
}
signed main(){
cin >>n;
for(int i = 1;i<= n;++i){
f[i] = i;//注意初始化
for(int j = 1,a;j<= n;++j){//读入
cin >>a;
if(i< j){
++tp;
r[tp].x = i,r[tp].y = j,r[tp].t = a;//添加边
}
}
}
sort(r + 1,r + tp + 1,cmp);//排序
for(int i = 1;i<= tp;++i){
int q = fi(r[i].x),p = fi(r[i].y);//找最老的祖先
if(q != p){
++sum;
f[q] = p;//认“爸爸”
ans += r[i].t;//加边权
}
if(sum == n - 1){//满足要求，退出
cout<< ans<< endl;
return 0;
}
}
return 0;
} 登录 - 沐枫OJhttps://www.mfstem.org/p/692我的AC代码：
#includeusing namespace std;
#define int long long
int n,tp,f[2005],sum,ans,m;
struct road{
int x;
int y;
int t;
}r[10005];
bool cmp(road a,road b){
return a.t< b.t;
}
int fi(int x){
return ((f[x] == x) ? x : f[x] = fi(f[x]));
}
signed main(){
cin >>n >>m;
for(int i = 1;i<= n;++i)f[i] = i;
for(int i = 1,p,xx,yx,tx;i<= m;++i){
cin >>p >>xx >>yx >>tx;
if(p == 1){
ans += tx;
int xxx = fi(xx),yyy = fi(yx);
if(xxx != yyy)f[xxx] = yyy,++sum;
}
else{
++tp;
r[tp].x = xx,r[tp].y = yx,r[tp].t = tx;
}
}
if(sum >= n - 1){
cout<< ans<< endl;
return 0;
}
// cout<< tp<< endl;
sort(r + 1,r + tp + 1,cmp);
for(int i = 1;i<= tp;++i){
// cout<< r[i].x<< " "<< r[i].y<< endl;
int q = fi(r[i].x),p = fi(r[i].y);
if(q != p){
f[q] = p;
ans += r[i].t;
++sum;
// for(int j = 1;j<= n;++j)cout<< f[j]<< " ";
// cout<< endl;
}
if(sum == n - 1){
cout<< ans<< endl;
return 0;
}
}
return 0;
} 代码我就不解释了，要做完才能看代码哟
下期讲讲基础A+B，敬请期待
拜了个拜！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
新闻名称：最小生成树Kruscal算法（C++）-创新互联
文章网址：http://scgulin.cn/article/ihgde.html
