test/aoj/GRL_2_A.boruvka.test.cpp

View this file on GitHub
Last update: 2024-01-08 13:32:33+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 <bits/stdc++.h>

#include "../../graph/mst.hpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int V, E;
    cin >> V >> E;
    vector<tuple<int, int, int>> G;
    for (int i = 0; i < E; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        G.emplace_back(s, t, w);
    }
    cout << boruvka(G, V).first << endl;
}

#line 1 "test/aoj/GRL_2_A.boruvka.test.cpp"
#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A"

#include <bits/stdc++.h>

#line 6 "graph/mst.hpp"

#line 4 "data-structure/unionfind/union_find.hpp"

class UnionFind {
   public:
    UnionFind() = default;
    explicit UnionFind(int n) : data(n, -1) {}

    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
};
#line 8 "graph/mst.hpp"

template <typename T>
using Edge = std::tuple<int, int, T>;

/*
 * Kruskal's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> kruskal(std::vector<Edge<T>> G, int V) {
    std::ranges::sort(G, {}, [](auto& e) { return std::get<2>(e); });
    UnionFind uf(V);
    T weight = 0;
    std::vector<Edge<T>> edges;
    for (auto& [u, v, w] : G) {
        if (!uf.same(u, v)) {
            uf.unite(u, v);
            weight += w;
            edges.push_back({u, v, w});
        }
    }
    return {weight, edges};
}

/*
 * Prim's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> prim(
    const std::vector<std::vector<std::pair<int, T>>>& G) {
    std::vector<bool> used(G.size());
    auto cmp = [](const auto& e1, const auto& e2) {
        return std::get<2>(e1) > std::get<2>(e2);
    };
    std::priority_queue<Edge<T>, std::vector<Edge<T>>, decltype(cmp)> pq(cmp);
    pq.emplace(0, 0, 0);
    T weight = 0;
    std::vector<Edge<T>> edges;
    while (!pq.empty()) {
        auto [p, v, w] = pq.top();
        pq.pop();
        if (used[v]) continue;
        used[v] = true;
        weight += w;
        if (v != 0) edges.push_back({p, v, w});
        for (auto& [u, w2] : G[v]) {
            pq.emplace(v, u, w2);
        }
    }
    return {weight, edges};
}

/*
 * Boruvka's Algorithm
 */
template <typename T>
std::pair<T, std::vector<Edge<T>>> boruvka(std::vector<Edge<T>> G, int V) {
    UnionFind uf(V);
    T weight = 0;
    std::vector<Edge<T>> edges;
    while (uf.size(0) < V) {
        std::vector<Edge<T>> cheapest(V,
                                      {-1, -1, std::numeric_limits<T>::max()});
        for (auto [u, v, w] : G) {
            if (!uf.same(u, v)) {
                u = uf.find(u);
                v = uf.find(v);
                if (w < std::get<2>(cheapest[u])) cheapest[u] = {u, v, w};
                if (w < std::get<2>(cheapest[v])) cheapest[v] = {u, v, w};
            }
        }
        for (auto [u, v, w] : cheapest) {
            if (u != -1 && !uf.same(u, v)) {
                uf.unite(u, v);
                weight += w;
                edges.push_back({u, v, w});
            }
        }
    }
    return {weight, edges};
}
#line 7 "test/aoj/GRL_2_A.boruvka.test.cpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int V, E;
    cin >> V >> E;
    vector<tuple<int, int, int>> G;
    for (int i = 0; i < E; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        G.emplace_back(s, t, w);
    }
    cout << boruvka(G, V).first << endl;
}