CPLib.TwoSat
Defined in cp-library@0.14.0
2-SAT問題
制約・計算量の n は変数の数、m は節の数を表します。
Values
namespace CPLib.TwoSat
add_clause
Type: Std::I64 -> Std::Bool -> Std::I64 -> Std::Bool -> CPLib.TwoSat::TwoSat -> CPLib.TwoSat::TwoSat
節 (a = f) or (b = g) を追加する
制約:0 <= a, b < n
計算量:ならしO(1)
Parameters
a: 変数1のインデックスf: 変数1の値(true/false)b: 変数2のインデックスg: 変数2の値(true/false)sat: 2-SAT問題
create
Type: Std::I64 -> CPLib.TwoSat::TwoSat
2-SAT問題を作る
計算量:O(n)
Parameters
n: 変数の数
solve
Type: CPLib.TwoSat::TwoSat -> Std::Option (Std::Array Std::Bool)
2-SAT問題を解く
計算量:O(n + m)
Returns
充足不能な場合はnone()。充足可能な場合はsome(arr)を返す。arr.@(i)は各リテラルの真偽値を表す。
Parameters
sat: 2-SAT問題
Types and aliases
namespace CPLib.TwoSat
TwoSat
Defined as: type TwoSat = unbox struct { ...fields... }
2-SAT問題の型
field n
Type: Std::I64
変数の数
field graph
Type: CPLib.Graph::Graph ()
グラフ