※ 引述《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