作者ericbibo (^^)
站內Prob_Solve
標題[請益] TWO Shortest Paths
時間Thu Jun 22 22:50:20 2006
由於一直沒人po文，所以我先po個已經困擾我很久的問題。
希望能吸引一點人氣。 (但願不會造成反效果...囧rz)
在ACM Problem 10806中，(
http://acm.uva.es/p/v108/10806.html )
我們必須從給定的起點 S 到終點 T 中，
找 "兩條" 沒有重疊的minimum weight shortest paths。
(也就是這兩條paths沒有經過相同的edges，且total weight值最小。)
可是，假如我現在把題目改成:
找"兩條"沒有重疊的minimum weight shortest paths，
一條由給定的起點 S1 到終點 D1，
另一條由起點 S2 到終點 D2 的話，
有沒有什麼方法可以解決這個問題呢?
我已經想這個問題好幾天了，
希望高手能不吝指教一下~ XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.82.205
1F：推 PsMonkey:恩... 先說說你的想法吧... (純路人) 203.204.16.17 06/22 22:55
2F：推 ericbibo:我試著用解10806的作法(max flow)去解 140.116.82.205 06/22 23:21
3F：→ ericbibo:可是都被我找到反例給推翻了，所以想請教 140.116.82.205 06/22 23:22
4F：→ ericbibo:大家的意見 140.116.82.205 06/22 23:23
5F：推 march20:然後 weight 依然要一樣嗎? 71.136.225.150 06/22 23:42
6F：推 ericbibo:兩條paths的weight不用一樣，可是weight 140.116.82.205 06/22 23:46
7F：→ ericbibo:的和加起來要最小 140.116.82.205 06/22 23:46
8F：推 march20:可以走到一樣的點, 但不能走相同的 edge 71.136.225.150 06/23 04:05
9F：推 march20:是這樣嗎? 71.136.225.150 06/23 04:05
10F：推 ericbibo:是的...你得到它了 ^_^ 59.104.152.115 06/23 12:04
11F：推 march20:有點懷疑這是 NP-hard problem 71.136.254.138 06/24 14:07