#include <bits/stdc++.h> using namespace std; #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A" #include "../graph/kruscal.cpp" #include "../template/const.hpp" int main() { int n, m; cin >> n >> m; Kruscal<int, INF> kru(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; kru.add_edge(a, b, c); } cout << kru.solve() << '\n'; return 0; }
#line 1 "test/kruscal.test.cpp" #include <bits/stdc++.h> using namespace std; #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A" #line 3 "graph/kruscal.cpp" using namespace std; #line 3 "data_structures/unionfind.cpp" using namespace std; // UnionFind // グループを管理するデータ構造 struct UnionFind { int n; vector<int> parents; UnionFind(int n) : n(n) { parents.assign(n, -1); } // find // xの親を返す. // 制約: 0 <= x < n int find(int x) { if (parents[x] < 0) return x; return parents[x] = find(parents[x]); } // unite // xとyを含むグループを併合 // 制約: 0 <= x,y < n void unite(int x, int y) { // xとyの含むグループを併合 int px = find(x); int py = find(y); if (parents[px] > parents[py]) swap(px, py); if (px != py) { parents[px] += parents[py]; parents[py] = px; } } // same // xとyが同じグループにいるか判定 // 制約: 0 <= x,y < n bool same(int x, int y) { return find(x) == find(y); } // size // xと同じグループのメンバーの個数 // 制約: 0 <= x < n int size(int x) { return -parents[find(x)]; } // root // 根を全て列挙する vector<int> root() { vector<int> res; for (int i = 0; i < n; i++) { if (parents[i] < 0) res.push_back(i); } return res; } // group_count // グループの数を返す. int group_count() { // ufのグループの数を数える return (int)root().size(); } }; #line 6 "graph/kruscal.cpp" // Kruscal // Kruscal法で最小全域森を求める. template <typename T, const T INF> struct Kruscal { struct edge { int a, b; T cost; int id; edge(int a, int b, T c, int id) : a(a), b(b), cost(c), id(id) {} }; int n; int m = 0; vector<edge> edges; vector<int> used_id; Kruscal(int n) : n(n) {} // add_edge // aからbへコストcの辺を張る void add_edge(int a, int b, T c) { edges.emplace_back(a, b, c, m++); } // solve // 最小全域森を求めて, そのコストを返す. // 計算量: O(|E|log|E|) T solve() { used_id.assign(m, 0); sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) { return a.cost < b.cost; }); T ans = T(0); UnionFind uf(n); for (const edge &e : edges) { if (uf.same(e.a, e.b)) continue; ans += e.cost; used_id[e.id] = 1; uf.unite(e.a, e.b); } return ans; } }; #line 2 "template/const.hpp" constexpr int INF = 1000'000'000; constexpr long long HINF = 4000'000'000'000'000'000; constexpr long long MOD = 998244353; constexpr double EPS = 1e-6; constexpr double PI = 3.14159265358979; #line 7 "test/kruscal.test.cpp" int main() { int n, m; cin >> n >> m; Kruscal<int, INF> kru(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; kru.add_edge(a, b, c); } cout << kru.solve() << '\n'; return 0; }