test/aoj/grl_2_a.test.cpp

View this file on GitHub
Last update: 2023-01-08 21:46:20+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

Depends on

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../../src/graph/kruskul.hpp"
#include "../../src/graph/template.hpp"

int main() {
  int V, E;
  cin >> V >> E;
  Kruskal<long long> kruskal(V);
  for (int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    kruskal.add_edge(s, t, d);
  }
  kruskal.build();
  cout << kruskal.get_cost_sum() << endl;
  return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/graph/kruskul.hpp"

#line 4 "src/graph/kruskul.hpp"
using namespace std;

#line 2 "src/structure/union_find_tree.hpp"

#line 4 "src/structure/union_find_tree.hpp"
using namespace std;

struct UnionFindTree {
private:
  int n;
  vector<int> parent, rank;

public:
  UnionFindTree(int n) : n(n), parent(n, -1), rank(n, 0) {}

  int root(int x) {
    if (parent[x] == -1) {
      return x;
    }
    return parent[x] = root(parent[x]);
  }

  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (rank[x] < rank[y]) {
      swap(x, y);
    }
    if (rank[x] == rank[y]) {
      ++rank[x];
    }
    parent[y] = x;
  }

  bool is_same(int x, int y) { return root(x) == root(y); }

  vector<vector<int>> groups() {
    vector<vector<int>> ret(n);
    for (int i = 0; i < n; i++) {
      ret[root(i)].emplace_back(i);
    }
    ret.erase(remove_if(begin(ret), end(ret),
                        [&](const vector<int> &v) { return v.empty(); }),
              end(ret));
    return ret;
  }
};
#line 2 "src/graph/template.hpp"

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 8 "src/graph/kruskul.hpp"

template <typename T> struct Kruskal {
private:
  int v;
  Edges<T> es;
  UnionFindTree uft;
  long long cost_sum = 0;
  Edges<T> ans_es;

public:
  Kruskal(int v) : v(v), uft(v) {}

  void add_edge(int from, int to, T cost) { es.emplace_back(from, to, cost); }

  void build() {
    sort(es.begin(), es.end(), [](const Edge<T> &e1, const Edge<T> &e2) {
      return e1.cost < e2.cost;
    });
    for (Edge<T> &e : es) {
      if (!uft.is_same(e.from, e.to)) {
        uft.unite(e.from, e.to);
        cost_sum += e.cost;
        ans_es.emplace_back(e);
      }
    }
  }

  T get_cost_sum() { return cost_sum; }

  Edges<T> get_edges() { return ans_es; }
};
#line 9 "test/aoj/grl_2_a.test.cpp"

int main() {
  int V, E;
  cin >> V >> E;
  Kruskal<long long> kruskal(V);
  for (int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    kruskal.add_edge(s, t, d);
  }
  kruskal.build();
  cout << kruskal.get_cost_sum() << endl;
  return 0;
}