[理工] 交大資演最後一題 aRLJ PTT批踢踢實業坊

作者: aRLJ (aRLJ) 2018-02-02 17:22:38

最後一題大家都有想到怎麼解嗎><？
題目大意是如果存在O(n^7)的演算法可以決定G是否存在Hamiltonian path，
要求設計不超過O(n^7)的演算法，決定G是否存在起終點皆不為x的Hamiltonian path
想破頭想不出來求解QQ

作者: Dora5566 (咩休幹某) 2018-02-02 17:24:00

印象中有在哪看過這題

作者: can18 (18號) 2018-02-02 17:26:00

想那題想半小時還是沒想出來QQ

作者: gary70812 (1) 2018-02-02 17:28:00

trace都來不及了 qq

作者: howard31622 (howard) 2018-02-02 17:45:00

我用大概n^2求的用兩次dfs就可以了

作者: TWkobe (中華柯比) 2018-02-02 17:46:00

不知道用ore's theorem可不可以

作者: devilkool (對貓毛過敏的貓控) 2018-02-02 17:49:00

我全部用DFS去掰

作者: howard31622 (howard) 2018-02-02 17:54:00

那題不難吧我覺得那題給你七次我還擔心他強迫你要用七次欸可是我try一下兩次就非常足夠了

作者: aRLJ (aRLJ) 2018-02-02 17:56:00

這不是NPC嗎><樓上求解!!

作者: d3dd2d (xml) 2018-02-02 18:03:00

加兩個點a,b連到除了x之外的所有點再加c點連到a d點連到b這樣如果有Hamiltonian path 也可以保證起終點不是x

作者: ken52011219 (呱) 2018-02-02 18:08:00

我也只想到ore’s theorem

作者: bibiwhistle (逼逼哨哨) 2018-02-02 18:10:00

總得過濾一下血統，不然進去一堆不會寫程式的推錯篇

作者: magic83v (R7) 2018-02-02 18:26:00

想的到n^7解法也是不容易

作者: arhtur945 (AnthonyBennet) 2018-02-02 20:22:00

我等等試試看，看來應該是我自己想不出來

作者: s06i06 (三條魚) 2018-02-02 20:30:00

很典型的reduction

作者: aRLJ (aRLJ) 2018-02-02 20:55:00

感謝~要來檢討一下為什麼想不到這樣的reduction了XD

作者: alan23273850 2018-02-02 21:03:00

題目超酷，典型的reduction

繼續閱讀