作者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/cn.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