作者changkh (留學生涯)
看板ck47th320
標題Re: [問題] 再一個演算法的問題
時間Mon Apr 4 10:19:32 2005
※ 引述《changkh (留學生涯)》之銘言：
: ※ 引述《genie2 (新挑戰)》之銘言：
: : 剛剛想到，這個問題是不是可以transform成：
: : 對每一個edge，assign weight 為 WB-WA
: : 然後對s到t，尋找是否有weight 大於 2 的路徑存在
: : 不知道有沒有幫助
: 嗯，除了s到t要weight大於2之外，路徑上的每一個點的weight也要
: 大於2。不過把兩個數字變成了一個之後問題似乎簡單許多。
不過到現在還是想不到怎麼做才好。
我想應該還是NP-complete的問題，可是要把哪一個問題reduce到它就不知道了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.43.196.35