7-6 最小生成树
\(1≤n≤2×10
5
,0≤m≤5×10
5
\)给定结点数为 n,边数为 m 的带权无向连通图 G,所有结点编号为 1,2, ⋯ ,n。
求 G 的最小生成树的边权和。
输入格式:
第一行两个正整数 n,m
之后的 m 行,每行三个正整数ui,vi,wi(1≤ui,vi≤n,0≤wi≤109),描述一条连接结点 ui 和 vi,边权为 wi 的边。
输出格式:
一个整数表示 G 的最小生成树的边权和。
输入样例:
7 12
1 2 9
1 5 2
1 6 3
2 3 5
2 6 7
3 4 6
3 7 3
4 5 6
4 7 2
5 6 3
5 7 6
6 7 1
输出样例:
16
数据范围与提示
\(1≤n≤2×10^5 ,0≤m≤5×10^5\)
简化版代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
int fa[N], n, m;
struct Node {
int u, v, w;
bool operator < (const Node & node) const {
return w < node.w;
}
} nd[N];
int find(int u)
{
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
for (int i = 1; i <= m; ++i) {
scanf("%d %d %d", &nd[i].u, &nd[i].v, &nd[i].w);
}
sort(nd + 1, nd + 1 + m);
long long ans = 0;
for (int i = 1; i <= m; ++i) {
int fu = find(nd[i].u);
int fv = find(nd[i].v);
if (fu == fv) continue;
fa[fu] = fv;
ans += nd[i].w;
}
printf("%lld", ans);
return 0;
}
中文注释版代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
int fa[N], n, m;
struct Node {
int u, v, w;
bool operator < (const Node &node) const {
return w < node.w;
}
} nd[N];
// 查找父节点(并查集)
int find(int u)
{
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
int main()
{
// 输入点数和边数
scanf("%d %d", &n, &m);
// 初始化并查集
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
// 输入边的信息
for (int i = 1; i <= m; ++i) {
scanf("%d %d %d", &nd[i].u, &nd[i].v, &nd[i].w);
}
// 将边按权值升序排序
sort(nd + 1, nd + 1 + m);
// Kruskal算法求最小生成树
long long ans = 0;
for (int i = 1; i <= m; ++i) {
int fu = find(nd[i].u);
int fv = find(nd[i].v);
// 如果两个节点不在同一连通分量中,则加入最小生成树
if (fu == fv) continue;
// 合并两个连通分量
fa[fu] = fv;
// 累加最小生成树的权值
ans += nd[i].w;
}
// 输出最小生成树的权值和
printf("%lld", ans);
return 0;
}
java版代码(有问题)
待补。。。
标签:10,const,int,最小,生成,fa,return,find From: https://www.cnblogs.com/aslwr/p/76-minimum-generation-tree-iasbv.html