Re: [問題] 請問一個問題
發現我忘了用 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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.52
討論串 (同標題文章)