※ 引述《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