作者JonathanWang (尹儿)
看板ACMCLUB
标题Re: [问题] 请问一个问题
时间Thu Oct 13 23:01:57 2005
※ 引述《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