好久沒認真Coding,露營烤要炸了= =。

把每一條邊當成一個點,如果兩條邊會交叉到的話,就要一條連裏面,另一條連外面。

因為只有 連裏面或外面兩種,所以可以弄成 2-SAT。

兩條邊會交叉的判斷,若 edge[1].u>edge[2].u && edge[1].v>edge[2].v && edge[1].u<edge[2].v ,

則可以知道他們無論 都連裏面 或 都連外面,都會交叉,所以必須 一個連外面,一個連裏面。

建邊 {i->j+m, j+m->i, j->i+m, i+m->j},求 SCC 後 2-SAT。

---------------------------------------------------------------------------------------

好久沒寫 2-SAT,簡單回憶一下。

若條件 a||b,則 建邊 {-a->b, -b->a}

求完 SCC,若有任意 a與-a 在同一個 SCC內 (blg[a]=blg[-a]),則條件不成立。

反之則 條件可成立。

---------------------------------------------------------------------------------------

我的code

http://codepad.org/6jcSdh0f

p.s: 我竟然犯了跟 momo校內賽 一樣的錯,rG打成G = =。

 

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()