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