Min-max semiring（(min, max) 半環）
(number/min_max_semiring.hpp)

• View this file on GitHub
• Last update: 2025-05-06 21:03:53+09:00
• Include: #include "number/min_max_semiring.hpp"

加法を min，乗法を max で定義した半環．零元は std::numeric_limits<T>::max()、単位元は std::numeric_limits<T>::min() となっていることに注意．例えば距離行列に載せて行列積をとることで，パス上の最大重みの最小化等に使用できる．

問題例

• AtCoder Beginner Contest 236 G - Good Vertices
• • No.1340 おーじ君をさがせ - yukicoder

Verified with

• linear_algebra_matrix/test/linalg_semirings.yuki1340.test.cpp
• number/test/min_max_semiring.test.cpp

Code

#pragma once
#include <limits>

// min-max 半環（加法が min, 乗法が max, 零元が INF, 単位元が -INF）
// Verified: abc236g, abc388f
template <class T> struct min_max_semiring {
    T val;
    min_max_semiring() : val(std::numeric_limits<T>::max()) {
        static_assert(std::numeric_limits<T>::max() > 0,
                      "std::numeric_limits<>::max() must be properly defined");
    }
    min_max_semiring(T x) : val(x) {}
    static min_max_semiring id() { return T(std::numeric_limits<T>::min()); }
    static min_max_semiring max() { return T(); }
    min_max_semiring operator+(const min_max_semiring &r) const {
        return (this->val > r.val ? r.val : this->val);
    }
    min_max_semiring &operator+=(const min_max_semiring &r) { return *this = *this + r; }
    min_max_semiring operator*(const min_max_semiring &r) const {
        return (this->val < r.val ? r.val : this->val);
    }
    min_max_semiring &operator*=(const min_max_semiring &r) { return *this = *this * r; }
    bool operator==(const min_max_semiring &r) const { return this->val == r.val; }
    bool operator!=(const min_max_semiring &r) const { return !(*this == r); }
    bool operator<(const min_max_semiring &r) const { return this->val < r.val; }
    bool operator>(const min_max_semiring &r) const { return this->val > r.val; }
    bool operator<=(const min_max_semiring &r) const { return this->val <= r.val; }
    bool operator>=(const min_max_semiring &r) const { return this->val >= r.val; }
    template <class OStream> friend OStream &operator<<(OStream &os, const min_max_semiring &x) {
        return os << x.val;
    }
};

#line 2 "number/min_max_semiring.hpp"
#include <limits>

// min-max 半環（加法が min, 乗法が max, 零元が INF, 単位元が -INF）
// Verified: abc236g, abc388f
template <class T> struct min_max_semiring {
    T val;
    min_max_semiring() : val(std::numeric_limits<T>::max()) {
        static_assert(std::numeric_limits<T>::max() > 0,
                      "std::numeric_limits<>::max() must be properly defined");
    }
    min_max_semiring(T x) : val(x) {}
    static min_max_semiring id() { return T(std::numeric_limits<T>::min()); }
    static min_max_semiring max() { return T(); }
    min_max_semiring operator+(const min_max_semiring &r) const {
        return (this->val > r.val ? r.val : this->val);
    }
    min_max_semiring &operator+=(const min_max_semiring &r) { return *this = *this + r; }
    min_max_semiring operator*(const min_max_semiring &r) const {
        return (this->val < r.val ? r.val : this->val);
    }
    min_max_semiring &operator*=(const min_max_semiring &r) { return *this = *this * r; }
    bool operator==(const min_max_semiring &r) const { return this->val == r.val; }
    bool operator!=(const min_max_semiring &r) const { return !(*this == r); }
    bool operator<(const min_max_semiring &r) const { return this->val < r.val; }
    bool operator>(const min_max_semiring &r) const { return this->val > r.val; }
    bool operator<=(const min_max_semiring &r) const { return this->val <= r.val; }
    bool operator>=(const min_max_semiring &r) const { return this->val >= r.val; }
    template <class OStream> friend OStream &operator<<(OStream &os, const min_max_semiring &x) {
        return os << x.val;
    }
};

Back to top page