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

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

概要

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

機能

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)

• $\min (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 minplus_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::min(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/min-plus-semiring.hpp"

#include <algorithm>
#include <climits>

namespace zawa {

template <class dat_type>
struct minplus_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::min(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