作者windows2k (KERORO军曹)
站内Prob_Solve
标题Re: [请益] TWO Shortest Paths
时间Thu Jun 22 23:24:28 2006
※ 引述《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
1F：推 ericbibo:可是这样会找到一条由S1到D2，一条却由 140.116.82.205 06/22 23:26
2F：→ ericbibo:S2到D1的paths 140.116.82.205 06/22 23:27
3F：推 windows2k:对喔, 在想想140.115.220.140 06/22 23:28
4F：推 SCSonic:XD 61.62.37.245 06/22 23:51
5F：推 windows2k:XDXD140.115.220.140 06/23 00:18
6F：推 bafu:XDXDXD 140.116.82.219 06/23 00:20