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