JakeLin

**Kruskal最小生成树**问题
**[Kruskal思路]**：每次拿出最权值最小的一边，若不构成环则将其选中，否则继续遍历
**[判断回环思路]**：设有一数组f，f[n]表示点n的祖先，初始各个点独立，所以均为其本身，若边的两个端点的祖先相同，则此边不能连接，否则将出现回环
代码如下：
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100 + 10;
const int maxn2 = maxn*(maxn-1)/2;
int f[maxn];
struct edge{  // 一条边 
	int a;   // 2端点+1权值+1状态 
	int b;
	int weight;
	int status;
}edges[maxn2];
int find(int x){  //找爹 
	return x==f[x]?x:(find(f[x]));
}
void init(int n,int m){
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
}
bool cmp(edge e1,edge e2){  //将边数组升序排序 
	return e1.weight<e2.weight;
}
int main(){
	int n;
	while(scanf("%d",&n)==1 && n!=0){
		int m = n*(n-1)/2;
		for(int i=0;i<m;i++){
			cin>>edges[i].a>>edges[i].b>>edges[i].weight;
		}
		init(n,m);
		sort(edges,edges+m,cmp);
		int ans = 0;
		for(int i=0;i<m;i++){
			if(edges[i].status==1) continue;
			int fa = find(edges[i].a);  //a的祖先 
			int fb = find(edges[i].b);  //b的祖先 
			if(fa!=fb){   //不是同一个祖先，相连不会成环 
				f[fa] = fb;  //相连（a的祖先【的祖先】是b的祖先） 
				ans+=edges[i].weight;  //修路加其权值 
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-同因查找（C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

众数问题（C语言代码）

三进制小数（C语言代码）

JakeLin-1729题-还是畅通工程-题解(C++代码)-简单易懂

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言考试练习题_排列（C语言代码）

剔除相关数（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

蚂蚁感冒（C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-同因查找 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

众数问题 （C语言代码）

三进制小数 （C语言代码）

JakeLin-1729题-还是畅通工程-题解(C++代码)-简单易懂

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言考试练习题_排列 （C语言代码）

剔除相关数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

蚂蚁感冒 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C二级辅导-同因查找（C语言代码）

众数问题（C语言代码）

三进制小数（C语言代码）

　　评论区

C语言考试练习题_排列（C语言代码）

剔除相关数（C语言代码）

【亲和数】（C语言代码）

蚂蚁感冒（C语言代码）