※ 引述《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