Skip to content

CPLib.TwoSat

Defined in cp-library@0.15.3

2-SAT問題

制約・計算量の n は変数の数、m は節の数を表します。

Examples

// 節 (x0 = true) or (x0 = true)(すなわち x0 = true)と、節 (x0 = false) or (x1 = true) を追加して解く
let sat = create(2).add_clause(0, true, 0, true).add_clause(0, false, 1, true);
assert_eq(|_|"", sat.solve, some([true, true]))

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の長さは変数の数で、arr.@(i)は変数iに割り当てる値を表す。

Parameters
  • sat : 2-SAT問題

Types and aliases

namespace CPLib.TwoSat

TwoSat

Defined as: type TwoSat = unbox struct { ...fields... }

2-SAT問題の型

Traits and aliases

Trait implementations