作者yalight (ㄚ光)
站内Prob_Solve
标题Re: [请益] TWO Shortest Paths
时间Sat Jun 24 17:31:36 2006
※ 引述《march20 ()》之铭言：
: Btw, 这个 reduction 看来不对喔.
: ※ 引述《yalight (ㄚ光)》之铭言：
: : 这问题应该可以 reduce 成 min-cost max-flow problem(更难).
: : 但是 min-cost max-flow 有 polynomial solution.
: : 所以可以证明这题不是 NP 问题...
: : reduce 方法:
: vvv 你是说 destination 吗?
不是 我是说全部的 edge
: : 就把他想成 source 的 capacity = 2, edge 的 capacity = 1,
: ^^^^^^ 今天讨论的是双 source 版本
我指的是题目的 S 那个 vertex,
反正要想成 max-flow 的 source 的话也很简单
capacity=2 capacity=∞
source ----------->
S=Graph=T -------------> sink
cost=0 cost=0
source 和 sink 是 max-flow 的
黄色是原题目的 graph
希望看的懂 orz
: : edge 上的 cost 就是 weight, 的 min-cost max-flow problem。
: 目前你的 reduction 看来不完整,
: 来问一个问题就可以知道你的 reduction 是怎麽一回事了.
: 呃, 找到 max-flow 之後, 试问原题对应的解为何?
min-cost
--
我画了一个很奇怪的图...orz
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.205.19