グラフ/Prim 法
(test/graph/prim.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• Prim 法 (include/emthrm/graph/prim.hpp)

Code

/*
 * @title グラフ/Prim 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/prim.hpp"

int main() {
  int v, e;
  std::cin >> v >> e;
  std::vector<std::vector<emthrm::Edge<long long>>> edge(v);
  while (e--) {
    int s, t, w;
    std::cin >> s >> t >> w;
    edge[s].emplace_back(s, t, w);
    edge[t].emplace_back(t, s, w);
  }
  std::cout << emthrm::prim(edge) << '\n';
  return 0;
}

#line 1 "test/graph/prim.test.cpp"
/*
 * @title グラフ/Prim 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/prim.hpp"



#include <functional>
#include <queue>
#line 7 "include/emthrm/graph/prim.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 9 "include/emthrm/graph/prim.hpp"

namespace emthrm {

template <typename CostType>
CostType prim(const std::vector<std::vector<Edge<CostType>>>& graph,
              const int root = 0) {
  const int n = graph.size();
  CostType res = 0;
  std::vector<bool> is_visited(n, false);
  is_visited[root] = true;
  std::priority_queue<Edge<CostType>,
                      std::vector<Edge<CostType>>,
                      std::greater<Edge<CostType>>> que;
  for (const Edge<CostType>& e : graph[root]) {
    if (e.dst != root) que.emplace(e);
  }
  while (!que.empty()) {
    const Edge<CostType> e1 = que.top();
    que.pop();
    if (is_visited[e1.dst]) continue;
    is_visited[e1.dst] = true;
    res += e1.cost;
    for (const Edge<CostType>& e2 : graph[e1.dst]) {
      if (!is_visited[e2.dst]) que.emplace(e2);
    }
  }
  return res;
}

}  // namespace emthrm


#line 12 "test/graph/prim.test.cpp"

int main() {
  int v, e;
  std::cin >> v >> e;
  std::vector<std::vector<emthrm::Edge<long long>>> edge(v);
  while (e--) {
    int s, t, w;
    std::cin >> s >> t >> w;
    edge[s].emplace_back(s, t, w);
    edge[t].emplace_back(t, s, w);
  }
  std::cout << emthrm::prim(edge) << '\n';
  return 0;
}

Back to top page