sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A" #include <bits/stdc++.h> #include "../../graph/mst.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int V, E; cin >> V >> E; vector<tuple<int, int, int>> edges; for (int i = 0; i < E; i++) { int s, t, w; cin >> s >> t >> w; edges.emplace_back(s, t, w); } cout << kruskal(edges, V).first << endl; }
#line 1 "test/aoj/GRL_2_A.kruskal.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A" #include <bits/stdc++.h> #line 6 "graph/mst.hpp" #line 4 "data-structure/unionfind/union_find.hpp" class UnionFind { public: UnionFind() = default; explicit UnionFind(int n) : data(n, -1) {} int find(int x) { if (data[x] < 0) return x; return data[x] = find(data[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (data[x] > data[y]) std::swap(x, y); data[x] += data[y]; data[y] = x; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -data[find(x)]; } private: std::vector<int> data; }; #line 8 "graph/mst.hpp" template <typename T> using Edge = std::tuple<int, int, T>; /* * Kruskal's Algorithm */ template <typename T> std::pair<T, std::vector<Edge<T>>> kruskal(std::vector<Edge<T>> G, int V) { std::ranges::sort(G, {}, [](auto& e) { return std::get<2>(e); }); UnionFind uf(V); T weight = 0; std::vector<Edge<T>> edges; for (auto& [u, v, w] : G) { if (!uf.same(u, v)) { uf.unite(u, v); weight += w; edges.push_back({u, v, w}); } } return {weight, edges}; } /* * Prim's Algorithm */ template <typename T> std::pair<T, std::vector<Edge<T>>> prim( const std::vector<std::vector<std::pair<int, T>>>& G) { std::vector<bool> used(G.size()); auto cmp = [](const auto& e1, const auto& e2) { return std::get<2>(e1) > std::get<2>(e2); }; std::priority_queue<Edge<T>, std::vector<Edge<T>>, decltype(cmp)> pq(cmp); pq.emplace(0, 0, 0); T weight = 0; std::vector<Edge<T>> edges; while (!pq.empty()) { auto [p, v, w] = pq.top(); pq.pop(); if (used[v]) continue; used[v] = true; weight += w; if (v != 0) edges.push_back({p, v, w}); for (auto& [u, w2] : G[v]) { pq.emplace(v, u, w2); } } return {weight, edges}; } /* * Boruvka's Algorithm */ template <typename T> std::pair<T, std::vector<Edge<T>>> boruvka(std::vector<Edge<T>> G, int V) { UnionFind uf(V); T weight = 0; std::vector<Edge<T>> edges; while (uf.size(0) < V) { std::vector<Edge<T>> cheapest(V, {-1, -1, std::numeric_limits<T>::max()}); for (auto [u, v, w] : G) { if (!uf.same(u, v)) { u = uf.find(u); v = uf.find(v); if (w < std::get<2>(cheapest[u])) cheapest[u] = {u, v, w}; if (w < std::get<2>(cheapest[v])) cheapest[v] = {u, v, w}; } } for (auto [u, v, w] : cheapest) { if (u != -1 && !uf.same(u, v)) { uf.unite(u, v); weight += w; edges.push_back({u, v, w}); } } } return {weight, edges}; } #line 7 "test/aoj/GRL_2_A.kruskal.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int V, E; cin >> V >> E; vector<tuple<int, int, int>> edges; for (int i = 0; i < E; i++) { int s, t, w; cin >> s >> t >> w; edges.emplace_back(s, t, w); } cout << kruskal(edges, V).first << endl; }