作者march20 ()
看板Prob_Solve
标题Re: [请益] TWO Shortest Paths
时间Sat Jun 24 17:08:15 2006
Btw, 这个 reduction 看来不对喔.
※ 引述《yalight (ㄚ光)》之铭言：
: ※ 引述《yalight (ㄚ光)》之铭言：
: : ^^^^^^ S 到 T 才对...囧
: 这问题应该可以 reduce 成 min-cost max-flow problem(更难).
: 但是 min-cost max-flow 有 polynomial solution.
: 所以可以证明这题不是 NP 问题...
: reduce 方法:
vvv 你是说 destination 吗?
: 就把他想成 source 的 capacity = 2, edge 的 capacity = 1,
^^^^^^ 今天讨论的是双 source 版本
: edge 上的 cost 就是 weight, 的 min-cost max-flow problem。
目前你的 reduction 看来不完整,
来问一个问题就可以知道你的 reduction 是怎麽一回事了.
呃, 找到 max-flow 之後, 试问原题对应的解为何?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.136.254.138
※ 编辑: march20 来自: 71.136.254.138 (06/24 17:08)
※ 编辑: march20 来自: 71.136.254.138 (06/24 17:10)