#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/prim.cpp" #include "../template/const.hpp" int main() { int n, m; cin >> n >> m; Prim<int, INF> prim(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; prim.add_edge(a, b, c); } cout << prim.solve() << '\n'; return 0; }
#line 1 "test/prim.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/prim.cpp" using namespace std; // Prim // Prim法で最小全域木を求める. template <typename T, const T INF> struct Prim { struct edge { int to; T cost; int id; edge(int to, T c, int id) : to(to), cost(c), id(id) {} }; function<bool(const edge &, const edge &)> compare = [](const edge &a, const edge &b) { return a.cost > b.cost; }; int n; int m = 0; vector<int> used_id; vector<vector<edge>> G; Prim(int n) : n(n) { G.resize(n); } // add_edge // aとbの間にコストcの無向辺をはる void add_edge(int a, int b, T c) { G[a].emplace_back(b, c, m); G[b].emplace_back(a, c, m++); } // solve // 最小全域木を求める. // 計算量: O(|E|log|V|) T solve() { used_id.assign(m, 0); T ans = T(0); vector<int> visited(n, 0); priority_queue<edge, vector<edge>, decltype(compare)> q{compare}; q.emplace(0, 0, -1); while (!q.empty()) { edge e = q.top(); q.pop(); if (visited[e.to]) continue; if (e.id >= 0) used_id[e.id] = 1; ans += e.cost; visited[e.to] = 1; for (const edge &e2 : G[e.to]) { if (visited[e2.to]) continue; q.push(e2); } } 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/prim.test.cpp" int main() { int n, m; cin >> n >> m; Prim<int, INF> prim(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; prim.add_edge(a, b, c); } cout << prim.solve() << '\n'; return 0; }