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