library-checker-problems
library-checker-problems copied to clipboard
Published
20 hours ago •
yosupo06
yosupo06
[問題案] Horn SAT
問題ID: horn_sat 問題名: Horn SAT
参考資料: https://www.slideshare.net/utatakiyoshi/ss-147867073 https://www.ioi-jp.org/joi/2020/2021-yo2/2021-yo2-t5-review.pdf
問題概要
N 変数 M 節の Horn SAT が与えられる。充足可能か判定し、可能ならば割り当てを一つ求めてください。
入力・出力
DIMACS 標準形式
制約
1 <= N <= 500000 1 <= M <= 500000 1 <= (リテラルの総数) <= 1000000
メモ
いろいろ 2-SAT (#26) に準ずる。
作業はできません
