7-2 最小生成树-kruskal_第一行包含两个整数 n(1<=n<=1x10 4 ),m(1<=m<=2x10 6 ) 表示该图共有

7-2 最小生成树-kruskal

//这题之诡异不在压缩路径，不在算法，只有30分的估计都少在了cin和scanf输入上。

分数 40

全屏浏览题目

切换布局

作者 任唯

单位 河北农业大学

题目给出一个无向连通图，要求求出其最小生成树的权值。

温馨提示：本题请使用kruskal最小生成树算法。

输入格式:

第一行包含两个整数 N(1<=N<=1x106),M(1<=M<=1x106) 表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi​,Yi​,Zi​ ，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​ 。

输出格式:

输出一个整数表示最小生成树的各边的长度之和。

输入样例:

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例:

7

代码长度限制

16 KB

时间限制

500 ms

内存限制

64 MB

#include<bits/stdc++.h>//转载留痕，cv的注意改一下行文
 
define shuiyun 66666666666
using namespace std;
 
struct edge {
	int u, v;
	int value;
}e[1000001];
 
int f[1000001];
 
int find(int x)
{
	if (x != f[x]) return f[x] = find(f[x]);
	return f[x];
}
 
bool cmp(edge a, edge b)
{
	return a.value < b.value;
}
 
int main() {
	int n, m, cnt = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].value);
	int num = 0, sum = 0;
	sort(e + 1, e + m + 1, cmp);
	for (int i = 1; i <= n; i++)f[i] = i;
	for (int i = 0; i <= m; i++)
	{
		int fu = find(e[i].u);
		int fv = find(e[i].v);
		if (fu != fv)
		{
			f[fu] = fv;
			sum += e[i].value;
			num++;
			if (num == n - 1)break;
		}
	}
	cout << sum;
}