Re: [請益] TWO Shortest Paths

[windows2k (KERORO軍曹)]

※ 引述《ericbibo (^^)》之銘言：
: 我們必須從給定的起點 S 到終點 T 中，
: 找 "兩條" 沒有重疊的minimum weight shortest paths。
: (也就是這兩條paths沒有經過相同的edges，且total weight值最小。)
: 可是，假如我現在把題目改成:
: 找"兩條"沒有重疊的minimum weight shortest paths，
: 一條由給定的起點 S1 到終點 D1，
: 另一條由起點 S2 到終點 D2 的話，
: 有沒有什麼方法可以解決這個問題呢?
我不是高手, 我只是來賺賭本的窮光蛋 囧rz
如果我沒搞錯題意的話
假設你會解原先的問題的話, 可以把後來這個問題轉成前一個問題
新增兩個節點, source 和 sink
新增四個邊 (source, S1) weight = 0, cap = 1  (u,v)代表一個從u到v的有向邊
           (source, S2) weight = 0, cap = 1
           (D1, sink) 同上
           (D2, sink) 一樣同上,
就把原來的問題轉成從 source 到 sink,
找 "兩條" 沒有重疊的minimum weight shortest paths
--
多打一點字, 看有沒有多一點批幣

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.115.220.140
推 ericbibo:可是這樣會找到一條由S1到D2，一條卻由
→ ericbibo:S2到D1的paths
推 windows2k:對喔, 在想想
推 SCSonic:XD
推 windows2k:XDXD
推 bafu:XDXDXD