Min-plus semiring / tropical semiring（(min, +) 半環・トロピカル半環）
(number/min_plus_semiring.hpp)

• View this file on GitHub
• Last update: 2022-01-25 23:19:52+09:00
• Include: #include "number/min_plus_semiring.hpp"
• Link: https://yukicoder.me/problems/no/1340

加法を min，乗法を + で定義した半環．零元は std::numeric_limits<T>::max() / 2 （オーバーフロー回避），単位元は 0 となっていることに注意．例えば距離行列に載せて行列積をとることで，パス長最小化等に使用できる．

なお，（当たり前ではあるが）零元と任意の値（正負に関わらず）との乗算の結果は零元になることに注意．

使用例

using R = min_plus_semiring<int>;
matrix<R> mat(N, N);

while (M--) {
    int a, b;
    cin >> a >> b;
    mat[b][a] = 0;
}

std::vector<R> initvec(N, R()); // R() == INF
initvec[0] = R::id(); // R::id() == 0
auto vec = mat.pow_vec(T, initvec);
cout << count(vec.begin(), vec.end(), R(0)) << '\n';

問題例

• No.1340 おーじ君をさがせ - yukicoder
• No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木 - yukicoder

Verified with

• linear_algebra_matrix/test/linalg_min_plus_semiring.yuki1780.test.cpp
• linear_algebra_matrix/test/linalg_semirings.yuki1340.test.cpp

Code

#include <limits>

// min-plus 半環・トロピカル半環（加法が min, 乗法が plus, 零元が INF, 単位元が 0）
// INF = numeric_limits<T>::max() / 2 を超えたら INF に clamp する
// Verified: https://yukicoder.me/problems/no/1340
template <class T> struct min_plus_semiring {
    T val;
    static const T _T_inf() {
        static_assert(std::numeric_limits<T>::max() > 0,
                      "std::numeric_limits<>::max() must be properly defined");
        return std::numeric_limits<T>::max() / 2;
    }
    min_plus_semiring() : val(_T_inf()) {}
    min_plus_semiring(T x) : val(x) {}
    static min_plus_semiring id() { return min_plus_semiring(0); }
    min_plus_semiring operator+(const min_plus_semiring &r) const {
        return (this->val > r.val ? r.val : this->val);
    }
    min_plus_semiring &operator+=(const min_plus_semiring &r) { return *this = *this + r; }
    min_plus_semiring operator*(const min_plus_semiring &r) const {
        if (this->val == _T_inf() or r.val == _T_inf()) return min_plus_semiring();
        T tmp = this->val + r.val; // Watch out for overflow
        return _T_inf() < tmp ? min_plus_semiring() : min_plus_semiring(tmp);
    }
    min_plus_semiring &operator*=(const min_plus_semiring &r) { return *this = *this * r; }
    bool operator==(const min_plus_semiring &r) const { return this->val == r.val; }
    bool operator!=(const min_plus_semiring &r) const { return !(*this == r); }
    bool operator<(const min_plus_semiring &x) const { return this->val < x.val; }
    bool operator>(const min_plus_semiring &x) const { return this->val > x.val; }
    template <class OStream> friend OStream &operator<<(OStream &os, const min_plus_semiring &x) {
        return os << x.val;
    }
};

#line 1 "number/min_plus_semiring.hpp"
#include <limits>

// min-plus 半環・トロピカル半環（加法が min, 乗法が plus, 零元が INF, 単位元が 0）
// INF = numeric_limits<T>::max() / 2 を超えたら INF に clamp する
// Verified: https://yukicoder.me/problems/no/1340
template <class T> struct min_plus_semiring {
    T val;
    static const T _T_inf() {
        static_assert(std::numeric_limits<T>::max() > 0,
                      "std::numeric_limits<>::max() must be properly defined");
        return std::numeric_limits<T>::max() / 2;
    }
    min_plus_semiring() : val(_T_inf()) {}
    min_plus_semiring(T x) : val(x) {}
    static min_plus_semiring id() { return min_plus_semiring(0); }
    min_plus_semiring operator+(const min_plus_semiring &r) const {
        return (this->val > r.val ? r.val : this->val);
    }
    min_plus_semiring &operator+=(const min_plus_semiring &r) { return *this = *this + r; }
    min_plus_semiring operator*(const min_plus_semiring &r) const {
        if (this->val == _T_inf() or r.val == _T_inf()) return min_plus_semiring();
        T tmp = this->val + r.val; // Watch out for overflow
        return _T_inf() < tmp ? min_plus_semiring() : min_plus_semiring(tmp);
    }
    min_plus_semiring &operator*=(const min_plus_semiring &r) { return *this = *this * r; }
    bool operator==(const min_plus_semiring &r) const { return this->val == r.val; }
    bool operator!=(const min_plus_semiring &r) const { return !(*this == r); }
    bool operator<(const min_plus_semiring &x) const { return this->val < x.val; }
    bool operator>(const min_plus_semiring &x) const { return this->val > x.val; }
    template <class OStream> friend OStream &operator<<(OStream &os, const min_plus_semiring &x) {
        return os << x.val;
    }
};

Back to top page