推 march20:這樣無法處理重複邊問題 71.137.9.203 06/24 03:30
推 march20:比如全部的點都在同一條線上 71.137.9.203 06/24 03:31
※ 引述《ericbibo (^^)》之銘言：
: 由於一直沒人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
我也來賺賭本..
如果我沒記錯的話 好像是這樣:
先找 S 到 T 的最短路徑, 假設是 cost1,
然後把這條最短路徑的方向反向, weight 變負的
(就是 max flow 那樣算 residual network)
然後再找 T 到 S 的最短路徑 cost2,
然後 cost1 + cost2 就是答案~
求最短路徑的方法可用 Dijkstra 還是偷懶用 Floyd Washall..
因為雖然會有 negative edge 但是不會有 negative cycle,
所以可以安心的用 @@:
有錯請指教 m(_ _)m
--
全賭法國隊了...orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.19