轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年3月23日 星期日

HOJ::Problem : 147 - 海綿寶寶之蟹堡餐飲聯盟(2-SAT)

2-STA問題。
http://hoj.twbbs.org.tw/judge/problem/view/147

2-STA問題是指一些布林值(true & false),透過設定他們的值讓一串運算是結果為true的方法。這題可以轉成,每個人是否當代表,新增4N個點,分別代表每間餐廳的兩個人和他們的相反情況,因為題目說一間餐廳一個人,所以先把每間餐廳每個人分別連到他們的相反(因為A出去就會導致B不出去),這些邊是雙向的關係,再來依照題目給的條件建邊,這裡只有單向的導致關係,最後用SCC縮點,先檢查每個人和每個人的相反有沒有在同一個SCC裡,有代表矛盾,沒有的話,因為編號小的SCC會導致編號大的SCC變成true,而我們發現每個人是否出去就是看哪邊SCC編號大(選小的會讓全部變成true,矛盾)。