2-SAT

點選打開連結

序言

　　

        最近花了一點心思研究2-sat模型，看了很多論文部落格等等，也在POJ上做了一點題。其實這個東西也還挺好玩的，當然，前提是每道題你都有認真分析，認真想清楚模型的意義，搞明白為什麼可以這樣，而不是簡單的知道怎樣做，就套上一個模闆了事，那樣，是不是也太糟蹋這門科學了。

　　關于2-sat，基本上所有人都會推薦兩個資料：

        伍昱 由對稱性解2-sat問題（ppt）

        趙爽 2-sat解法淺析（pdf）

        我當然也會推薦啦，好歹這也是引導我入門的東西，雖然說一開始看的并不是很懂，不過，還是要先膜拜一下兩位大牛。

　　這篇文章主要是把我對2-sat的一些研究進行總結，我不太喜歡公式化的語言，是以，基本上會是白話陳述，主要包括以下五個内容：

       1、概念的闡述

       2、算法的闡述

       3、算法的解釋

       4、構圖的介紹

　　5、題目的分享

　　下面就進入正題。

概念

　　

       要知道2-sat是什麼，我們先要知道什麼是适定性（Satisfiability）問題，适，就是合适，定，就是确定，适定性問題通俗的說就是确定是否可以滿足所有的條件？或者說就是确定一個滿足所有條件的方案。取英文的前三個字母，簡稱sat問題。

　　通俗的sat問題表述一般是這樣的：有很多個集合，每個集合裡面有若幹元素，現給出一些取元素的規則，要你判斷是否可行，可行則給出一個可行方案。如果所有集合中，元素個數最多的集合有k個，那麼我們就說這是一個k-sat問題，同理，2-sat問題就是k=2時的情況。

　　為什麼研究2-sat呢？無可置疑的是它很有用。為什麼不研究3-sat乃至k更大的情況呢，因為它們已經被證明為是 NP完全問題了，在更多的情況下，2-sat不僅僅是元素個數最多的集合含有2個元素，而是每個集合都含有2個元素，且這2個元素不允許同時取出，這篇文章主要讨論的就是這樣一種特殊的模型。

算法

　　

       仍然這樣，我的總結也從這道題開始。

　　題目大意：一國有n個黨派，每個黨派在議會中都有2個代表，現要組建和平委員會，要從每個黨派在議會的代表中選出1人，一共n人組成和平委員會。已知有一些代表之間存在仇恨，也就是說他們不能同時被選為和平委員會的成員，現要你判斷滿足要求的和平委員會能否創立？如果能，請任意給出一種方案。（ POI 0106 ）

　　正如你看到的那樣，題目給的非常裸，其實，2-sat的題目都沒有隐藏的那麼深，不像網絡流那樣很難發現。

　　對于這個問題，暴力當然可以解決了，其實說的更好聽一點，也就是在圖上進行暴力，噗，是不是感覺很進階的樣子，嗯，這其實就是一個很容易了解的算法了。

　　

算法一：持之以恒

　　假設1A、1B為1号黨的兩名黨員，2A、2B（噗，不準笑）為2号黨的兩名黨員，且1A與2A之間存在仇恨！那麼，這意味着什麼？如果選擇1A，就隻能選擇2B了，如果選擇了2A呢？那同理就隻能選擇1B了，那麼，我們可以這樣建構一個圖，在1A到2B之間搭上一條邊，2A到1B之間搭上一條邊，這條邊的含義就是：必須。

　　也就是說，沿着一條路徑，如果一個點被選擇了，那麼這條路徑以後的點都将被選擇，那麼，出現不可行的情況就是，存在一個黨派兩個黨員都被選擇了，那麼，我們隻需要枚舉一下就可以了，資料不大，答案總是可以出來的。

　　這麼一個簡單的算法，放在第一個說，看來你已經知道它不是重點了，但是，若題目要求的是字典序最小的方案的話，那就隻能選擇這個算法了。

算法二：沒有名字

　　構圖還是跟第一個算法一樣，但是在解圖的過程中進行了非常漂亮的優化。

　　為了說清楚傳遞，我們先來回憶一下命題的概念：命題、逆命題、否命題、逆否命題。

       概念就不說了，舉了例子也好：

　　命題：三角形内角和為180°

　　逆命題：内角和為180°的是三角形

　　否命題：不是三角形的内角和不為180°

　　逆否命題：内角和不是180°的不是三角形

　　有個很顯然的結論就是，命題與逆否命題的真假性是一樣的（又有人要說我啰嗦了嗯）

　　也許，你正在很奇怪我為什麼要扯到這個東西，雖然我看的所有資料都沒有介紹過，也沒人把這兩東西扯到一起，不過，我還就真覺得它們就是一路的，怎麼說？

　　選A就必須選B，那麼我們先“逆一下”，從B到A，再“否一下”，不選B就一定不選A，這是顯然成立的，也就是說，在構好的圖中，“必須”是沿着邊正方向傳遞下去的，“禁止”是沿着邊反方向傳遞下去的，那麼每次我們選擇了一個點，就把它的對立點（即同集合的另一進制素）标記為不可選，然後呢，我們把選擇标記正向傳遞，再把禁止标記逆向傳遞，這是符合題意的高效做法，但是……還是很麻煩，竟然要雙向傳遞，而且……你怎麼知道一開始要選擇哪一個節點才好呢？囧。

　　不要急，請先達成一點共識：

       1、如果很多節點已經處在一個強連通分量内了，也就是它們兩兩均可互達了，那麼意味着選擇了其中的一個，整個強連通分量都将被選擇，如果不選擇其中的一個，那麼整個強連通分量内都不能夠被選擇。

       2、如果一個集合的兩個元素處在了同一個強連通分量内，也就是說要麼都不選，要麼都被選，那麼題目要求的選出一個就一定無法成立了。

　　3、題中不管給出哪兩個不能同時選，都不能改變我們連的邊都是對稱的這一事實，隻要A到B有邊，那麼B的對立節點到A的對立節點就有邊。

　　4、邊的對稱意味着圖的對稱，原圖的對稱意味着哪怕用強連通分量縮點後的圖一樣對稱，是以對立節點的概念也可以應用在強連通分量上。

　　5、為了叙述友善，以下簡稱強連通分量為塊，注意：真正的塊指的是點雙連通分量，這裡隻是一種形象化的表述，是不規則的！

算法的過程如下：

構圖

　　更具體的後面再說

縮點

　　Tarjan算法縮點，将所有的邊反過來（ 為什麼？後面有嗯 ）

判可行

　　枚舉集合的兩個元素，看其是否處于不同的塊内，若否的話則給出不可行資訊

記錄沖突

　　這裡所說的沖突不是題中給出的兩個人之間有仇恨，那樣的邊是實際存在，我們這裡說的沖突是指若兩個塊分别含有兩個對立節點，也就是說一個集合的兩個元素分布在了兩個不同的塊中，那麼這兩個塊就是沖突的，即不可能同時被選擇，這樣一種沖突關系是不存在于邊中的，是不依賴于輸入的資料的，我們要找到與一個塊對立的塊，并把它們儲存下來。

拓撲排序

　　将縮點後的圖進行拓撲排序（排的是塊而不是節點）

構造方案

　　按照拓撲序列的順序，依次通路所有塊，若一個塊未被标記，将其标記為“選擇”，不傳遞“選擇”标記，将被選塊的對立塊标記為“不選擇”，将其“不選擇”标記沿着邊正向傳遞。（ 不是逆着邊麼？哼，圖已經被反過來了，你到底有沒有認真看呐！囧 ）

　　沒了？沒了，真沒了。我知道你很想問為什麼，= =，ps：是不是覺得我特别啰嗦……

唉，啰嗦慣了，看到那些 “一 點 都 不 啰 嗦 的 論 文 我 就 想 * * ”。回到正題，我們繼續。

解釋

1、為什麼要用反邊存縮點後的圖？

- - 考慮到算法傳遞标記的時候，“選擇”标記是沒有進行傳遞的，也就是說正向邊是沒有利用到的，傳遞的都是“不選擇”标記，也就是說走的都是反邊，但是，鄰接表存邊，怎麼走得了反邊呢？那麼既然正向邊沒有用，就把整個圖反過來存就好了，并且，這個反圖還真是反得好啊！為什麼呢，往下看。

2、為什麼要拓撲排序呢？

- - 不該來的還是來了，這可真是一個令人惡心的問題，哪怕到我現在寫，我也無法對它有種深深的認同，你懂的，有些東西，哪怕你并說不出它為什麼如此，但是你能感受到，能夠認同到，能夠抓住它的走向，深信其的正确，但是，有的東西，哪怕你已經能夠說出為什麼了，還是無法對其有深深的認同感，總覺得有種别扭、不舒服的感覺在，少廢話，繼續。

- - 觀察下面的這幅圖（注意：此圖為原圖，非縮點後存的反圖）

　　如果我們沒有按照拓撲序列來選擇塊的話：通路到A，發現其無标記，于是把它标記為可選擇，然後把A’标記為不可選擇，然後呢，進行标記傳遞，但是問題出現了，若進行“選擇”标記傳遞，則B和B’将被标記為選擇，若進行“不選擇”标記傳遞，則B和B’将被标記為不選擇，這又選擇又不選擇的，不就沖突了嗎？難道是因為此圖無解嗎？但是根據我們判斷無解的标準，即兩對立節點處在同一塊中，此圖是有解的，不存在節點可以互達，究其原因，是因為我們的構造方法不對，A處在了整個邊的上遊地帶，先就将其确定為選擇對原圖的影響太大了，根本就無法保證接下來還能進行正确的抉擇。是以，正确的方法應該是按照拓撲順序，從影響小的開始抉擇，在轉成反邊後，A’會處在拓撲序列的首位，将A’标記為選擇，将A标記為不選擇，都不能傳遞，再将B标記為選擇，B’标記為不選擇，當然，将B标記為不選擇，B’标記為選擇也是可以的，這完全看拓撲排序的編寫規則，畢竟我們是通路到一個無标記的就将其标記為選擇的，那麼誰先出現誰就被選擇了，自然界的規律哈哈。

3、為什麼隻傳遞“不選擇”标記，不傳遞“選擇”标記？

- - 還記得我們的選擇規則嗎？好像已經重複了好多遍了……找到一個未被标記的，就将其标記為選擇，然後将對立塊标記為不選擇，再把不選擇标記傳遞，如果我們選擇了B，那麼它的後代節點A’（此處為原圖的後代，即上圖所示）一定是被選擇了的？為什麼呢？如果它的後代節點A’是沒有被選擇的，那麼它的後代節點的對立節點A肯定是被選擇了的，根據邊的對稱性，A’是B的後代節點，那麼B’就是A的後代節點，既然A被選擇了，那麼B’也要被選擇，那麼根據順序，B會被标記為不可選擇，那麼我們在通路到B的時候，就不會把它認定為未标記，那也就不存在将其标記為選擇了，這與假設是沖突的，顯然不可行。是以，既然我們選擇一個節點的時候，它的後代都已經被選擇好了，那麼我們就不需要進行“選擇”标記的傳遞了，況且，到标記傳遞的時候，我們都已經存的是反圖了，就算你想傳遞也沒辦法了……囧。總的來說，就是雖然我們沒有傳遞選擇标記，但是這種傳遞的性質是滿足的。

4、标記法構造方案的時候為什麼不會同時標明一個集合的兩個元素？

- - 嗯，我想這跟上一個問題是一樣的，如果你還心存疑惑，Please read it again.

5、标記法構造方案的時候為什麼不會把同一集合兩個元素都标記為不選擇？

- - 我們不妨把選擇一個塊，然後将其對立塊标記為不選擇這一行為叫做直接标記，把其對立塊進行“不選擇”标記傳遞時标記塊叫做間接标記，下面就容易說話了……

（1）若兩對立塊是在某塊被标記為選擇後，同時被其直接标記為不選擇的：

　　那麼我們想想它們為什麼會被其直接标記？當然是因為它們的内部有與标記為選擇的塊對立的節點，在記錄沖突這一步驟中被記錄了下來，是以才會這樣的，但是再定睛一看，憑什麼被标記為選擇的塊中某兩節點的對立節點分布在了不同的塊中？還記得我們達成的共識嗎？邊的對稱意味着塊的對稱，那麼這兩個被直接标記為不選擇的塊本就不應該分開，這種情況是不成立的。也就是說，這兩個被标記為“不可選”的塊不都是直接标記的。

　　這同時還說明了很重要的一點，與一個塊直接沖突的塊存在且僅存在一個，是以我們記錄沖突塊用的不是鄰接表，而隻是一個數組就可以了。

（2）若兩對立塊是在某塊被标記為選擇後，其中一個塊被其直接标記，另一塊被其間接标記：

       因為其中一塊被其直接标記，故其間存在一對對立節點，另一塊與被直接标記的這一塊為對立塊（根據大前提），那麼又出現了存在于被直接标記的塊中的兩個節點，它們的對立節點分散在了兩個塊中，這又沖突了。也就是說，這兩個被标記為“不選擇”的塊都不是被直接标記的。

（3）若兩對立塊是在某塊被标記為選擇後，同時被其間接标記為不可選擇的：

　　這麼說來，被标記為選擇的塊的對立塊（假設為O），它到這兩個塊（假設為A，A’）都是有路徑的，因為要進行不選擇标記傳遞啊（此處為反圖叙述），但是根據圖的對稱性，既然O到A有路徑，那麼A’就到O，然而，O到A’也有路徑，那麼兩個塊就顯然是一個塊，這是與假設相悖的。也就是說，這兩個被标記為“不可選”的塊也都不是間接标記的。

　　那麼，總的來說，在将一個塊标記為“選擇”之後，在直接标記與間接标記中都不會出現上述情況。那在不同的塊被标記為“選擇”之後，會出現上述情況嗎？

（4）在整個操作中會把兩個對立塊都标記為不選擇嗎？

　　至此，我們已經可以确定的就是，在一次選擇與傳遞過程中，是不會出現這樣的情況的，若是放在整個的構造過程中，我們也可以确信的就是，兩個對立塊的任何一個都不會被别的塊直接标記為不可選，如果一個塊已經被标記為不可選了，那麼隻能是它的對立塊被标記為可選了，才将其直接标記，同時，那些可能再度将其标記為不可選的塊，會在它的間接标記下，死亡……嗯，也就是被奪去标記别人的資格，為什麼？因為圖是對稱的！

這個問題就這樣愉快的解決了！

6、都說用對稱性解決2-sat問題，到底哪裡用到了對稱性？

- - 是的，這個問題真的是太蠢的，不知道你是不是有跟我一樣的想法，至少我就糾結過好久，唉，讓我再感歎一次吧！愚蠢的問題啊！算法雖然沒有直接用到對稱性來實作，但是對稱性是算法的基石啊！如果原圖不是對稱的！那前面的證明就都不成立，那麼算法正确性就無法保證了！真是太2的問題了，誰說一定要在算法過程中展現才叫用到啊，唉，真是2死了。

模型

　　

       當然，我還是很希望你看到這裡已經懂了的，不然，肯定是我叙述的太沒水準了。= = 如果不懂的話，還是弄懂再往下走為妙，畢竟，（詞乏了，略去）

　　如果你以為2-sat就隻是和平委員會這樣的題目的話，那你就錯了，但是，你以為它比和平委員會多很多的話，那你也錯了，其實，常用的模型沒有太多。

模型一：兩者（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連邊，要的不僅是拓撲序，還有判可行與否。在2-sat圖當中，若該圖是可行的，就意味着如果從A到A’有路徑的話，A’到A是沒有路徑的，因為如果有路徑，它們就成一個塊了，不會被判為可行，那麼，如果A到A’是有路徑的話，在反圖中，A’就到A有路徑，那麼拓撲裡，A’就會因為靠前被标記為“選擇”，并未滿足條件。并且，我們應當确信的是，解的多情況依賴的是拓撲排序的多情況，不按拓撲序來的話，解就是錯誤的，或者說是不成立的，也就是說，我們拓撲序先選擇A的話，就會導緻别的限制條件的不成立，那麼在我們引入了A’到A的這條邊後，A就與A’在同一塊中了，算法會報告不可行資訊。若是原圖本來就滿足A到A’有路徑，然而A’到A無路徑的話，我們添一條邊，隻是确定了其有解，但絲毫不會影響到拓撲排序，隻有當A到A’之間根本不存在路徑的時候，才會影響到其拓撲排序，是以，真相是這樣的。

　　是不是有人已經開始疑惑，講了這麼久的對稱性，整個算法都是依賴對稱性才得以成立的，那麼怎麼一下引入一條邊讓圖不對稱了算法還成立呢！關于這個問題，其實很好解釋，仔細想想，對稱性確定的是什麼？它確定的可是原圖有解，則一定可以構造出來。現在我們引入了一條邊A’→A，若通過上述判斷，讓其無解了，那麼對後面顯然是沒有影響的，畢竟算法都沒執行下去了，還算什麼影響。如果還有解呢？這說明了什麼？這說明了A’到A原本就存在一條路徑，或者A’到A之間根本就沒有路徑。如果有路徑的話，那麼我多增加一條有差別嗎？它會影響到算法的任何一步嗎？顯然不會啊，那如果原本沒有路徑的話呢？沒有路徑意味着誰在拓撲序列中靠前都是可能的，在有了該邊後（反邊為A→A’），A将在拓撲序列中靠前，被标記為“選擇”，那麼我們會對A’進行直接标記，此時，A’到A是沒有路可走的，它根本就無法通路到A，是以在标記的這個過程中，這條路徑根本就沒有影響到圖的任何對稱性，在拓撲排序後，你完全可以當其不存在。

　　模型其實都大同小異，還是看自己去變幻，比如模型一和模型二其實就是一樣的，隻是針對的點不同而已。一般，如果2-sat感覺很明顯的話，就用2-sat做好了，不過，千萬記得考慮好如何降低構圖的複雜度噢！複雜度如果太高，就還是再另辟蹊徑吧，也許有更加好的方法嗯。

題目

　　

        都源自POJ，大家可以自行練習，如果要對拍什麼的，這裡也有程式，題目按從簡單到簡單的順序排序（噗……其實是推薦做題順序），大家，一起好好加油。

        POJ 3207

        POJ 3683

        POJ 3678

        POJ 3648

        POJ 2723

        POJ 2749