发现我忘了用 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