test/aoj/GRL_2_A.test.cpp

View this file on GitHub
Last update: 2021-08-01 23:46:19+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A"
#include "../../graph/mst-kruskal.hpp"

#include <iostream>
using namespace std;

using edge = Edge<int>;
int main() {
  vector<edge> edges;
  int V, E;
  cin >> V >> E;
  for (int i = 0; i < E; ++i) {
    int x, y, w;
    cin >> x >> y >> w;
    edges.emplace_back(x, y, w);
  }
  int ans = kruscal(V, edges);
  cout << ans << endl;
}

#line 1 "test/aoj/GRL_2_A.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A"
#line 1 "graph/mst-kruskal.hpp"
/**
 * @title 最小全域木 (クラスカル法)
 */
#include <algorithm>
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

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

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 1 "datastructure/union-find-tree.hpp"
/**
 * @title Union-Find
 */
#line 5 "datastructure/union-find-tree.hpp"

class UnionFind {
public:
  std::vector<int> data; // sizeとparを同時に管理する
  UnionFind(int size) : data(size, -1) {}
  int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
  void unite(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
      if (data[py] < data[px]) std::swap(px, py);
      data[px] += data[py]; data[py] = px;
    }
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -data[find(x)]; }
};
#line 7 "graph/mst-kruskal.hpp"

template< typename T >
T kruscal(int V, Edges< T > &edges) {
  // 最小全域木の重みを返す
  UnionFind uf(V);
  T weight = 0;
  std::sort(edges.begin(), edges.end());
  for (auto e : edges) {
    if (uf.same(e.from, e.to)) continue;
    uf.unite(e.from, e.to);
    weight += e.cost;
  }
  return weight;
}
#line 3 "test/aoj/GRL_2_A.test.cpp"

#line 5 "test/aoj/GRL_2_A.test.cpp"
using namespace std;

using edge = Edge<int>;
int main() {
  vector<edge> edges;
  int V, E;
  cin >> V >> E;
  for (int i = 0; i < E; ++i) {
    int x, y, w;
    cin >> x >> y >> w;
    edges.emplace_back(x, y, w);
  }
  int ans = kruscal(V, edges);
  cout << ans << endl;
}