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的其他文章

你可能喜欢

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

A+B for Input-Output Practice (VII) （C++代码）

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

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

C语言训练-计算一个整数N的阶乘（C语言代码）

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

评论区

精彩推荐

ASCII帮了大忙

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

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

Wu-求圆的面积（C++代码）

DNA （C语言描述，数据结构）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

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

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

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

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

zjh

TA的其他文章

你可能喜欢

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

A+B for Input-Output Practice (VII) （C++代码）

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

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

C语言训练-计算一个整数N的阶乘 （C语言代码）

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

评论区

精彩推荐

ASCII帮了大忙

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

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

Wu-求圆的面积 （C++代码）

DNA （C语言描述，数据结构）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

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

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

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

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

C语言训练-计算一个整数N的阶乘（C语言代码）

　　评论区

Wu-求圆的面积（C++代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）