作者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