[問題] facebook puzzle: facebull
看板Prob_Solve (計算數學 Problem Solving)作者seedman (cc)時間14年前 (2010/05/01 15:30)推噓2(2推 0噓 5→)留言7則, 2人參與討論串1/1
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
推
05/01 22:44, , 1F
05/01 22:44, 1F
→
05/01 22:44, , 2F
05/01 22:44, 2F
→
05/01 22:44, , 3F
05/01 22:44, 3F
→
05/02 10:01, , 4F
05/02 10:01, 4F
推
05/02 10:48, , 5F
05/02 10:48, 5F
→
05/09 00:34, , 6F
05/09 00:34, 6F
→
05/09 00:34, , 7F
05/09 00:34, 7F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12
