[問題] UVA 11294 wedding

作者: BombCat (炸彈貓)   2013-05-13 11:37:44
題目:http://tinyurl.com/d7v6yar
code:http://ideone.com/v11UOE
這題看起來是2SAT的變形,給婚禮客人在長方形桌兩側安排座位
有兩個限制
1.同一對夫婦不能做同一側
2.有外遇關係的不能一起被新娘看到,而新娘不會看到坐同一側的人
我寫了一個簡單的2SAT sovler,先把新娘位置安排好
然後iW表第i對夫婦中的老婆是否跟新娘坐一方用1表示,否則就是0
找出是否可以滿足限制。
不過上傳到UVA得到WA,我試過網路上和我自己產生的測試資料結果
可以satisfiable的都會有輸出一組解,不能的都會輸出"bad luck"
不知道哪裡不對,希望大大們能給點提示。
UVA討論板掛了,真不方便。

Links booklink

Contact Us: admin [ a t ] ucptt.com