max-plus-semiring (max+)
(src/utility/semiring/max-plus-semiring.hpp)

• View this file on GitHub
• Last update: 2023-01-15 13:12:13+09:00
• Include: #include "src/utility/semiring/max-plus-semiring.hpp"

概要

$\R\ \cup\ {-\infin }$ 上での $\max$ と $+$ についての半環 を扱う構造体。トロピカル半環 とも呼ばれる。

機能

zawa::normal_semiring<T>

• T 扱いたい集合

T id_add

• -std::numeric_limits<T>::max

T id_mul

• 0

T add(const T& a, const T& b)

• $\max (a, b)$

T mul(const T& a, const T& b)

• $a\ +\ b$
• $\infin$ をid_addとしているため、丸めこみが発生します。

Code

#pragma once

#include <algorithm>
#include <climits>

namespace zawa {

template <class dat_type>
struct maxplus_semiring {
	using T = dat_type;
	static constexpr T id_add = -std::numeric_limits<T>::max();
	static constexpr T id_mul = 0;
	static T add(const T& a, const T& b) {
		return std::max(a, b);
	}
	static T mul(const T& a, const T& b) {
		if (b > 0 or a > id_add - b) {
			return a + b;
		}
		else {
			return id_add;
		}
	}
};

} // namespace zawa

#line 2 "src/utility/semiring/max-plus-semiring.hpp"

#include <algorithm>
#include <climits>

namespace zawa {

template <class dat_type>
struct maxplus_semiring {
	using T = dat_type;
	static constexpr T id_add = -std::numeric_limits<T>::max();
	static constexpr T id_mul = 0;
	static T add(const T& a, const T& b) {
		return std::max(a, b);
	}
	static T mul(const T& a, const T& b) {
		if (b > 0 or a > id_add - b) {
			return a + b;
		}
		else {
			return id_add;
		}
	}
};

} // namespace zawa

Back to top page