drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ 2-SAT 制約条件:2-SAT 密グラフ グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る テーマ解説記事 スラック変数 SAT 結論 先に結論から。 リテラル に対して、以下の条件 A, B, C は同値である。 A： のうち、True であるのは 1 個以下である B：任意の () に対して、節 を充足する C：新たなリテラル の値を適切に定めたとき、以下をすべて充足する 1：節 () 2：節 () 3：節 () 背景 リテラル のうち、True であるのは高々 1 個であるという条件を、2-SAT で記述することを考える。 なお、この条件は、 を 0-1 変数とみなしたときに、 tex: X_{0} + X_{1} + \dots + X_{N-1} \le 1] とも言い換えられる。 さて、上述の条件は、各 ()… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F08%2F04%2F021846" title="2-SAT で密な節を解消する方法 - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2023-08-04 02:18:46 rich https://drken1215.hatenablog.com/entry/2023/08/04/021846 1.0 100%