zjh

```cpp
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"

using namespace std;

typedef long long ll;
const int maxn = 100010;
const int INF = 1e9;

//priority_queue<int, vector<int>, greater<int> > q;

typedef struct {
	int x, y, val;
}Edge;

vector<Edge> E;	//存图
int n, m, fa[maxn];	//fa : 并查集数组

//初始化fa数组
void init() {
	for(int i = 1; i <= n; ++i) fa[i] = i;
}

//找爹函数
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

//排序cmp
bool cmp(Edge a, Edge b) {
	return a.val < b.val;
}

//kruskal核心代码
int kruskal() {
	init();
	sort(E.begin(), E.end(), cmp);	//按照成本从小到大排序
	int res = 0;	//结果
	//枚举排序后的每条边
	for(int i = 0; i < m; ++i) {
		int p1 = find(E[i].x);	//找到E[i].x的祖宗
		int p2 = find(E[i].y);	//找到E[i].y的祖宗
		if(p1 != p2) {	//如果它俩祖宗不一样，那么就合并任意一个
			fa[p2] = p1;	//并
			res += E[i].val;	//加上合并x，y的成本
			n--;	//最小生成树构造的边只有n - 1条边
		}
		if(n == 1) {	//边已经够n - 1条了，可以退出循环了
			break;
		}
	}
	E.clear();	//多组数据输入，要清空vector数组
	return res;
}

int main() {
	while(true) {
		cin >> n;
		if(n == 0) break;
		m = (n * (n - 1)) / 2;
		for(int i = 0; i < m; ++i) {
			int x, y, z, k;
			cin >> x >> y >> z >> k;
			if(k) z = 0;	//这里注意，k = 1说明x - y的公路已建，那么成本就是0
			Edge e = {x, y, z};
			E.push_back(e);
		}
		cout << kruskal() << endl;
	}
	return 0;
}
```

0.0分

1 人评分

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

zjh

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

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

简单的a+b （C语言代码）

【密码】（C语言代码）

继续畅通工程-题解(C++代码) kruskal最小生成树

评论区

精彩推荐

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

简单的a+b （C语言代码）

校门外的树（C语言代码）

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

用筛法求之N内的素数。（C语言代码）

简单的a+b （C语言代码）

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

字符逆序（C语言代码）

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

拆分位数（C语言代码）

zjh

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

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

简单的a+b （C语言代码）

【密码】 （C语言代码）

继续畅通工程-题解(C++代码) kruskal最小生成树

评论区

精彩推荐

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

简单的a+b （C语言代码）

校门外的树 （C语言代码）

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

用筛法求之N内的素数。 （C语言代码）

简单的a+b （C语言代码）

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

字符逆序 （C语言代码）

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

拆分位数 （C语言代码）

【密码】（C语言代码）

　　评论区

校门外的树（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符逆序（C语言代码）

拆分位数（C语言代码）