作者seedman (cc)
站内Prob_Solve
标题[问题] facebook puzzle: facebull
时间Sat May 1 15:30:04 2010
http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=1
题目简单的讲就是说
他给你一堆不同weight的directed edge Mx
每条edge可以把Ca连到Cb
求minimum weight edge set让图变成strong connected component
我一开始的想法是把同一个点当起点和终点时看成两个不同的点
然後找{起点set} {终点set}的minimum weight perfect matching
後来发现这是错的
例如我可能会找到这种
C1 \/ C1
C2 /\ C2
C3 \/ C3
C4 /\ C4
虽然是minimum weight perfect matching但是这些edge在原图不能造成SCC
因为C1没有办法变成C3,C4
另外还有下面这种例子
M1 C1 C2 1
M2 C2 C1 2
M3 C1 C3 3
M4 C3 C1 4
M5 C2 C3 100
用matching去找的话会找到3条edge的解
但是这题最佳解是1 2 3 4这4条edge
有人知道这要往哪方面想吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.42.231.186
1F：推 FRAXIS:component要可以互相连通成为strongly connected 05/01 22:44
2F：→ FRAXIS:应该是会需要一个path 从起点开始 遍历所有点 然後又回起点 05/01 22:44
3F：→ FRAXIS:你是要找这种path的最小值? 05/01 22:44
4F：→ seedman:不是 因为算cost只有加进去的时候算 走的时候可以走很多次 05/02 10:01
5F：推 FRAXIS:听起来是minimum spanning strong connected subgraph问题 05/02 10:48
6F：→ seedman:goo一下好像不是用approximation就是和题意不同的 05/09 00:34
7F：→ seedman:看来不是一个已知解法的问题 XD 05/09 00:34