verify/aoj-ALDS1_12_A.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A

Depends on

• Prim's Algorithm（最小全域木） (algorithm/Graph/Others/prim.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A"

#include <iostream>

#include "../algorithm/Graph/Others/prim.hpp"

int main() {
    int n;
    std::cin >> n;

    algorithm::Prim<int> prim(n);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            int a;
            std::cin >> a;

            if(i < j and a != -1) prim.add_edge(i, j, a);
        }
    }

    auto ans = prim.prim();
    std::cout << ans << std::endl;
}

#line 1 "verify/aoj-ALDS1_12_A.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A"

#include <iostream>

#line 1 "algorithm/Graph/Others/prim.hpp"



/**
 * @brief Prim's Algorithm（最小全域木）
 * @docs docs/Graph/Others/prim.md
 */

#include <cassert>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

namespace algorithm {

template <typename T>
class Prim {
    std::vector<std::vector<std::pair<int, T> > > m_g;  // m_g[v][]:=(ノードvの隣接リスト). pair of (to, cost).

public:
    Prim() : Prim(0) {}
    explicit Prim(size_t vn) : m_g(vn) {}

    // ノード数を返す．
    int order() const { return m_g.size(); }
    // 重み付き無向辺を張る．
    void add_edge(int u, int v, T cost) {
        assert(0 <= u and u < order());
        assert(0 <= v and v < order());
        m_g[u].emplace_back(v, cost);
        m_g[v].emplace_back(u, cost);
    }
    // 重み付き無向連結グラフにおける最小全域木のコストを求める．O(|E|*log|V|).
    T prim(int rt = 0) {
        assert(0 <= rt and rt < order());
        T res = 0;
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, std::greater<std::pair<T, int> > > pque;
        pque.emplace(0, rt);
        std::vector<bool> seen(order(), false);
        while(!pque.empty()) {
            auto [cost, u] = pque.top();
            pque.pop();
            if(seen[u]) continue;
            seen[u] = true;
            res += cost;
            for(const auto &[v, cost] : m_g[u]) {
                if(!seen[v]) pque.emplace(cost, v);
            }
        }
        return res;
    }
};

}  // namespace algorithm


#line 6 "verify/aoj-ALDS1_12_A.test.cpp"

int main() {
    int n;
    std::cin >> n;

    algorithm::Prim<int> prim(n);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            int a;
            std::cin >> a;

            if(i < j and a != -1) prim.add_edge(i, j, a);
        }
    }

    auto ans = prim.prim();
    std::cout << ans << std::endl;
}

Back to top page