※ 引述《chhsiao (bye~)》之銘言： : 發現我忘了用 s, 所以沒轉文過來 ^^" : --- : ※ 引述《vcore (vcore)》之銘言： : : 請各位大大幫忙~ : : 問題如下: : : 有一個矩陣 4*4矩陣 : : 例如 : : 15 0 0 5 : : 0 50 20 30 : : 35 5 0 15 : : 0 65 50 70 : : 請求出最少線段覆蓋 全部的"0" : : ( 線段是以覆蓋整個row或整個col ) : : 例如 : : 15-0-35-0 這條線段覆蓋了2個0 : : 15-0-0-5 覆蓋2個0 : : 35-5-0-15 覆蓋一個0 : : 所以上面這個例子 最少要用3個線段覆蓋全部的0 : : 給定N*N矩陣 : : 求出最少需幾條線段覆蓋全部的"0" : : N <= 100 : : 請問各位這題要用什麼演算法? : : 謝謝! : 這題可以 reduce 成 bipartite graph 的 vertex cover : (reduce 的方法就如 windows2k 所說) : 而有個定理說 bipartite graph 的 maximum size of a matching : 等於 minimum size of a vertex cover : 不過我還在讀, 所以還不會 :p 想出來了. 先找一個 maximum matching M, 令 Q <- {}, 任取一個 unmatched vertex x (i.e. x is not in M), 然後把所有 x 連到的點加到 Q 裡面, (這些點一定在 M 裡面, why? :p) 並把這些點及它們在 M 裡面的對應點從 M 之中去掉, 這樣一來又會產生一些 unmatched vertices. 重複這個步驟直到沒有 unmatched vertex, 此時把剩餘的 M 裡面其中一個 bipart 加到 Q 中. Q 就是一組 minimum vertex cover. --- 書上的證明是給 vertex cover => matching. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.52