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