test/kruscal.test.cpp
Depends on
Code
#include <bits/stdc++.h>
using namespace std;
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"
#include "../graph/kruscal.cpp"
#include "../template/const.hpp"
int main() {
int n, m;
cin >> n >> m;
Kruscal<int, INF> kru(n);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
kru.add_edge(a, b, c);
}
cout << kru.solve() << '\n';
return 0;
}
#line 1 "test/kruscal.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"
#line 3 "graph/kruscal.cpp"
using namespace std;
#line 3 "data_structures/unionfind.cpp"
using namespace std;
// UnionFind
// グループを管理するデータ構造
struct UnionFind {
int n;
vector<int> parents;
UnionFind(int n) : n(n) {
parents.assign(n, -1);
}
// find
// xの親を返す.
// 制約: 0 <= x < n
int find(int x) {
if (parents[x] < 0) return x;
return parents[x] = find(parents[x]);
}
// unite
// xとyを含むグループを併合
// 制約: 0 <= x,y < n
void unite(int x, int y) { // xとyの含むグループを併合
int px = find(x);
int py = find(y);
if (parents[px] > parents[py]) swap(px, py);
if (px != py) {
parents[px] += parents[py];
parents[py] = px;
}
}
// same
// xとyが同じグループにいるか判定
// 制約: 0 <= x,y < n
bool same(int x, int y) {
return find(x) == find(y);
}
// size
// xと同じグループのメンバーの個数
// 制約: 0 <= x < n
int size(int x) {
return -parents[find(x)];
}
// root
// 根を全て列挙する
vector<int> root() {
vector<int> res;
for (int i = 0; i < n; i++) {
if (parents[i] < 0) res.push_back(i);
}
return res;
}
// group_count
// グループの数を返す.
int group_count() { // ufのグループの数を数える
return (int)root().size();
}
};
#line 6 "graph/kruscal.cpp"
// Kruscal
// Kruscal法で最小全域森を求める.
template <typename T, const T INF>
struct Kruscal {
struct edge {
int a, b;
T cost;
int id;
edge(int a, int b, T c, int id) : a(a), b(b), cost(c), id(id) {}
};
int n;
int m = 0;
vector<edge> edges;
vector<int> used_id;
Kruscal(int n) : n(n) {}
// add_edge
// aからbへコストcの辺を張る
void add_edge(int a, int b, T c) {
edges.emplace_back(a, b, c, m++);
}
// solve
// 最小全域森を求めて, そのコストを返す.
// 計算量: O(|E|log|E|)
T solve() {
used_id.assign(m, 0);
sort(edges.begin(), edges.end(),
[](const edge &a, const edge &b) { return a.cost < b.cost; });
T ans = T(0);
UnionFind uf(n);
for (const edge &e : edges) {
if (uf.same(e.a, e.b)) continue;
ans += e.cost;
used_id[e.id] = 1;
uf.unite(e.a, e.b);
}
return ans;
}
};
#line 2 "template/const.hpp"
constexpr int INF = 1000'000'000;
constexpr long long HINF = 4000'000'000'000'000'000;
constexpr long long MOD = 998244353;
constexpr double EPS = 1e-6;
constexpr double PI = 3.14159265358979;
#line 7 "test/kruscal.test.cpp"
int main() {
int n, m;
cin >> n >> m;
Kruscal<int, INF> kru(n);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
kru.add_edge(a, b, c);
}
cout << kru.solve() << '\n';
return 0;
}
Back to top page