Re: [問題] 請問一個問題
※ 引述《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
討論串 (同標題文章)