本文只做總結性說明 2 SAT 2 SAT是k SAT問題的一種，k SAT問題在$k =3$時已經被證明是NP完全問題 2 SAT問題定義比較簡單 有n個布爾變數$x_1 x_n$。給出$m$個限制關係，每個關係最多只對兩個變數進行限制。求一組取值使得滿足所有限制。 這裡的限制例如：選$A$必選$ ...
本文只做總結性說明
2-SAT
2-SAT是k-SAT問題的一種，k-SAT問題在\(k>=3\)時已經被證明是NP完全問題
2-SAT問題定義比較簡單
有n個布爾變數\(x_1-x_n\)。給出\(m\)個限制關係，每個關係最多只對兩個變數進行限制。求一組取值使得滿足所有限制。
這裡的限制例如：選\(A\)必選\(B\) 或是 \(A,B\)至少選一個
解決方法
2-SAT問題所構成的圖具有對稱性
對於兩個點來說
即若選\(A\)必選\(B\)，那麼選\(B\)必選\(A\)
根據這種性質，前人總結出了一種方法
將一個點\(A\)拆為\(A,A'\)
1.若選\(A\)必選\(B\)，那麼從\(A\)向\(B\)連一條邊
2.tarjan縮點(把時間從\(O(NM)\)優化至\(O(n)\))
3.判斷是否\(A'A\)是否在同一強聯通分量中
對於需要輸出方案的題目
4.根據縮完點的圖，建出其反圖
5.對反圖進行拓撲排序
6.根據拓撲排序的順序標記答案
經典模型
- 兩者（A，B）不能同時取
那麼選擇了A就只能選擇B’，選擇了B就只能選擇A’
連邊A→B’，B→A’
- 兩者（A，B）不能同時不取
那麼選擇了A’就只能選擇B，選擇了B’就只能選擇A
連邊A’→B，B’→A
- 兩者（A，B）要麼都取，要麼都不取
那麼選擇了A，就只能選擇B，選擇了B就只能選擇A，選擇了A’就只能選擇B’，選擇了B’就只能選擇A’
連邊A→B，B→A，A’→B’，B’→A’
- 兩者（A，A’）必取A
連邊A’→A
\(A'A\)不能同時出現，選\(A'\)必選\(A\)，故只能單獨選\(A\)
例題
由簡單到簡單2333
