Re: [問題] 請問一個問題
※ 引述《LPH66 (運命のルーレット廻して)》之銘言：
: ※ 引述《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
: : 請問各位這題要用什麼演算法?
: : 謝謝!
: 印象中這題隨機客老師好像在前年的IOI營中有提出來過....
: (只是改成修理電路板的型式)
: 記得當時老師說這個題目是NPC?
: 當然前年的事要記錯也是很容易的 所以如果有錯還請指正 Orz
我以為這和 bipartite-matching 問題是一樣的,
但不記得怎麼轉了..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.44
討論串 (同標題文章)