[理工] 交大資演最後一題

看板Grad-ProbAsk作者 (aRLJ)時間7年前 (2018/02/02 17:22), 編輯推噓11(11推 0噓 11→)
留言22則, 14人參與, 7年前最新討論串1/1
最後一題大家都有想到怎麼解嗎><？ 題目大意是如果存在O(n^7)的演算法可以決定G是否存在Hamiltonian path， 要求設計不超過O(n^7)的演算法，決定G是否存在起終點皆不為x的Hamiltonian path 想破頭想不出來求解QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.252.253 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1517563361.A.88E.html
推
02/02 17:24, 7年前 , 1F
印象中有在哪看過這題
02/02 17:24, 1F
推
02/02 17:26, 7年前 , 2F
想那題想半小時還是沒想出來QQ
02/02 17:26, 2F
推
02/02 17:28, 7年前 , 3F
trace都來不及了 qq
02/02 17:28, 3F
推
02/02 17:45, 7年前 , 4F
我用大概n^2求的
02/02 17:45, 4F
→
02/02 17:45, 7年前 , 5F
用兩次dfs就可以了
02/02 17:45, 5F
推
02/02 17:46, 7年前 , 6F
不知道用ore's theorem可不可以
02/02 17:46, 6F
推
02/02 17:49, 7年前 , 7F
我全部用DFS去掰
02/02 17:49, 7F
推
02/02 17:54, 7年前 , 8F
那題不難吧
02/02 17:54, 8F
→
02/02 17:54, 7年前 , 9F
我覺得那題給你七次
02/02 17:54, 9F
→
02/02 17:54, 7年前 , 10F
我還擔心他強迫你要用七次欸
02/02 17:54, 10F
→
02/02 17:54, 7年前 , 11F
可是我try一下兩次就非常足夠了
02/02 17:54, 11F
→
02/02 17:56, 7年前 , 12F
這不是NPC嗎><樓上求解!!
02/02 17:56, 12F
推
02/02 18:03, 7年前 , 13F
加兩個點a,b連到除了x之外的所有點 再加c點連到a d點連到b
02/02 18:03, 13F
→
02/02 18:04, 7年前 , 14F
這樣如果有Hamiltonian path 也可以保證起終點不是x
02/02 18:04, 14F
→
02/02 18:08, 7年前 , 15F
我也只想到ore’s theorem
02/02 18:08, 15F
推
02/02 18:10, 7年前 , 16F
總得過濾一下血統，不然進去一堆不會寫程式的
02/02 18:10, 16F
→
02/02 18:11, 7年前 , 17F
推錯篇
02/02 18:11, 17F
→
02/02 18:26, 7年前 , 18F
想的到n^7解法也是不容易
02/02 18:26, 18F
→
02/02 20:22, 7年前 , 19F
我等等試試看，看來應該是我自己想不出來
02/02 20:22, 19F
推
02/02 20:30, 7年前 , 20F
很典型的reduction
02/02 20:30, 20F
→
02/02 20:55, 7年前 , 21F
感謝~要來檢討一下為什麼想不到這樣的reduction了XD
02/02 20:55, 21F
推
02/02 21:03, 7年前 , 22F
題目超酷，典型的reduction
02/02 21:03, 22F
‣ 更多 aRLJ 的文章
文章代碼(AID): #1QT2tXYE (Grad-ProbAsk)