※ 引述《changkh (留学生涯)》之铭言： : ※ 引述《changkh (留学生涯)》之铭言： : : 嗯，除了s到t要weight大於2之外，路径上的每一个点的weight也要 : : 大於2。不过把两个数字变成了一个之後问题似乎简单许多。 : 不过到现在还是想不到怎麽做才好。 : 我想应该还是NP-complete的问题，可是要把哪一个问题reduce到它就不知道了。 昨天晚上睡觉时半梦半醒之间突然想出来了。 那时候只看到一只乌龟从眼前走过，就晃然大悟了。 是这样做的，把longest path reduce到它。 假设longest path的问题是在一个graph之中，给两点s, t，是否有一个 路径长大於k。 那麽我可以在这图之外加一个点，若叫做u，在t-u之间加一个weight， 它的值是-k。那麽如果s到u的路径存在，s-t之中必有一条路径其长度 大於k。 为什麽看到乌龟会想到这个解法呢？因为乌龟的壳看起来就像一个graph， 而它的尾巴让我想到可以加一个edge，让它的值是-k，这样就可以了。 我是这样猜想的。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 211.75.133.138