lwx20211103 @ 2023-07-03 22:48:55
#include <bits/stdc++.h>
using namespace std;
struct graph
{
int u, v, c;
} gra[214514];
int fa[214514], tot, sum;
int n, m;
bool cmp(graph a, graph b)
{
return a.c < b.c;
}
int _find(int x)
{
return (x == fa[x] ? x : fa[x] = _find(fa[x]));
}
void _merge(int u, int v)
{
int x = _find(u), y = _find(v);
if (x != y)
fa[x] = y;
}
void kru()
{
for (int i = 1; i <= m; i++)
{
int a = _find(gra[i].u), b = _find(gra[i].v);
if (a == b) continue;
_merge(a, b);
sum += gra[i].c;
tot++;
if (tot == n - 1) return;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, c;
cin >> u >> v >> c;
gra[i].u = u, gra[i].v = v, gra[i].c = c;
}
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
sort(gra + 1, gra + 1 + m, cmp);
kru();
cout << sum;
return 0;
}
结构体遍历图懵逼中。
by SnapYust @ 2023-07-03 22:57:03
@lwx20211103 卷题佬
by SnapYust @ 2023-07-03 23:01:25
@lwx20211103 用一个变量来存边的数量,每合并一次就++,当算完以后变量还是小于 orz
by SnapYust @ 2023-07-03 23:02:04
@lwx20211103
for (int i = 1; i <= m; i++)
{
if (Union (e[i].u, e[i].v))
{
ans += e[i].w;
cnt++;
if (cnt == n - 1)
{
cout << ans;
return 0;
}
}
}
cout << "orz" << endl;
return 0;
by lwx20211103 @ 2023-07-04 12:35:45
@SnapYust 你是不是没有看到标题(
by toolazy @ 2023-08-07 19:57:21
并查集吧,最方便了,正好Kruskal也会用到并查集,最后查一下是不是所有节点都是同一个根(蒟蒻别打qwq