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