Test/Graph/Normal/Kruskal.test.cpp

• View this file on GitHub
• Last update: 2025-06-14 20:53:47+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

Depends on

• Library/DataStructure/DisjointSetUnion.hpp
• Library/Graph/Graph.hpp
• Library/Graph/Normal/Kruskal.hpp

Code

#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"

#include "./../../../Library/Graph/Normal/Kruskal.hpp"


#include <iostream>


#include "./../../../Library/Graph/Graph.hpp"


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  int n, m;
  cin >> n >> m;

  auto graph = mtd::Graph(n);
  for (int i = 0; i < m; ++i) {
    int s, t, w;
    cin >> s >> t >> w;
    graph.addEdge(s, t, w);
  }

  auto min_spanning_tree = mtd::kruskal(graph);

  ll ans = 0;
  for (const auto& [f, t, c] : min_spanning_tree.getEdges()) {
    if (f < t) { ans += c; }
  }
  cout << ans << endl;
}

#line 1 "Test/Graph/Normal/Kruskal.test.cpp"
#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"

#line 2 "Library/Graph/Normal/Kruskal.hpp"

#include <queue>


#line 2 "Library/DataStructure/DisjointSetUnion.hpp"

#include <iostream>

#include <numeric>

#include <vector>


namespace mtd {

  template <class T = int>
  class PotentialDisjointSetUnion {
    std::vector<int> m_root;
    std::vector<int> m_rank;
    std::vector<int> m_size;
    std::vector<T> m_potential;

  public:
    PotentialDisjointSetUnion() = delete;
    PotentialDisjointSetUnion(int n)
        : m_root(n), m_rank(n), m_size(n, 1), m_potential(n) {
      std::iota(m_root.begin(), m_root.end(), 0);
    }

    auto unite(int x, int y, T p = 0) {
      p += potential(x);
      p -= potential(y);
      x = root(x);
      y = root(y);
      if (x == y) { return false; }
      if (m_rank[x] < m_rank[y]) {
        std::swap(x, y);
        p = -p;
      }
      if (m_rank[x] == m_rank[y]) { ++m_rank[x]; }
      m_size[x] = m_size[y] = size(x) + size(y);
      m_root[y] = x;
      m_potential[y] = p;
      return true;
    }

    auto root(int x) -> int {
      if (m_root[x] == x) { return x; }
      int r = root(m_root[x]);
      m_potential[x] += m_potential[m_root[x]];
      return m_root[x] = r;
    }

    auto potential(int x) -> T {
      root(x);
      return m_potential[x];
    }

    auto size(int x) -> int {
      if (m_root[x] == x) { return m_size[x]; }
      return size(m_root[x] = root(m_root[x]));
    }

    auto isSame(int x, int y) { return root(x) == root(y); }

    auto diff(int x, int y) { return potential(y) - potential(x); }

    friend std::ostream& operator<<(std::ostream& os,
                                    const PotentialDisjointSetUnion& dsu) {
      for (const auto& x : dsu.m_root) { os << x << " "; }
      return os;
    }
  };
}  // namespace mtd

#line 2 "Library/Graph/Graph.hpp"
#include <deque>

#line 4 "Library/Graph/Graph.hpp"
#include <ranges>

#include <tuple>

#line 7 "Library/Graph/Graph.hpp"

namespace mtd {
  template <class Node = long long, class Cost = long long>
  class Graph {
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

  public:
    Graph(int n) : m_n(n), m_graph(n) {}
    Graph(const std::vector<Edges>& edges)
        : m_n(edges.size()), m_graph(edges) {}
    Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v);
        } else {
          addEdge(u, v);
        }
      }
    }
    Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v, c] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v, c);
        } else {
          addEdge(u, v, c);
        }
      }
    }

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
      addArc(f, t, c);
      addArc(t, f, c);
    }
    auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
      m_graph[f].emplace_back(t, c);
    }
    auto getEdges(const Node& from) const {
      class EdgesRange {
        const typename Edges::const_iterator b, e;

      public:
        EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
        auto begin() const { return b; }
        auto end() const { return e; }
      };
      return EdgesRange(m_graph[from]);
    }
    auto getEdges() const {
      std::deque<std::tuple<Node, Node, Cost>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, c] : getEdges(from)) {
          edges.emplace_back(from, to, c);
        }
      }
      return edges;
    }
    auto getEdgesExcludeCost() const {
      std::deque<std::pair<Node, Node>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, _] : getEdges(from)) {
          edges.emplace_back(from, to);
        }
      }
      return edges;
    }
    auto reverse() const {
      auto rev = Graph<Node, Cost>(m_n);
      for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
      return rev;
    }
    auto size() const { return m_n; };
    auto debug(bool directed = false) const {
      for (const auto& [f, t, c] : getEdges()) {
        if (f < t || directed) {
          std::cout << f << " -> " << t << ": " << c << std::endl;
        }
      }
    }
  };
}  // namespace mtd

#line 7 "Library/Graph/Normal/Kruskal.hpp"

namespace mtd {
  template <class Node, class Cost>
  auto kruskal(const Graph<Node, Cost>& graph) {
    auto n = graph.size();
    auto min_spanning_tree = Graph<Node, Cost>(n);

    auto dsu = PotentialDisjointSetUnion(n);
    using Type = std::pair<Cost, std::pair<Node, Node>>;
    std::priority_queue<Type, std::vector<Type>, std::greater<Type>> q;
    for (const auto& [f, t, c] : graph.getEdges()) {
      q.emplace(c, std::make_pair(f, t));
    }

    while (!q.empty()) {
      auto [cost, ft] = q.top();
      auto [from, to] = ft;
      q.pop();
      if (dsu.isSame(from, to)) { continue; }
      dsu.unite(from, to);
      min_spanning_tree.addEdge(from, to, cost);
    }

    return min_spanning_tree;
  }
}  // namespace mtd

#line 5 "Test/Graph/Normal/Kruskal.test.cpp"

#line 7 "Test/Graph/Normal/Kruskal.test.cpp"

#line 9 "Test/Graph/Normal/Kruskal.test.cpp"

using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  int n, m;
  cin >> n >> m;

  auto graph = mtd::Graph(n);
  for (int i = 0; i < m; ++i) {
    int s, t, w;
    cin >> s >> t >> w;
    graph.addEdge(s, t, w);
  }

  auto min_spanning_tree = mtd::kruskal(graph);

  ll ans = 0;
  for (const auto& [f, t, c] : min_spanning_tree.getEdges()) {
    if (f < t) { ans += c; }
  }
  cout << ans << endl;
}

Back to top page