[問題] facebook puzzle: facebull

[seedman (cc)]

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
推 FRAXIS:component要可以互相連通成為strongly connected
→ FRAXIS:應該是會需要一個path 從起點開始 遍歷所有點 然後又回起點
→ FRAXIS:你是要找這種path的最小值?
→ seedman:不是 因為算cost只有加進去的時候算 走的時候可以走很多次
推 FRAXIS:聽起來是minimum spanning strong connected subgraph問題
→ seedman:goo一下好像不是用approximation就是和題意不同的
→ seedman:看來不是一個已知解法的問題 XD