[理工] 交大资演最后一题 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

继续阅读