题意:有一个n*n的矩阵,在矩阵上有m个行星,一个武器能够消灭同一行或者同一列的星星
求最小的要用多少武器消灭全部的星星
思路:把方阵看做一个特殊的二分图(以行列分别作为两个顶点集V1、V2,当中|V1|=|V2|)
然后把每行x或者每列y看成一个点,而障碍物(x,y)能够看做连接x和y的边。依照这样的思路建图,问题就转化成为选择最少的一些点(x或y)。使得从这些点与全部的边相邻,事实上这就是最小点覆盖问题。
最小点覆盖数 = 最大匹配数
这样本题就转化为求最大匹配数了
题意:有一个n*n的矩阵,在矩阵上有m个行星,一个武器能够消灭同一行或者同一列的星星
求最小的要用多少武器消灭全部的星星
思路:把方阵看做一个特殊的二分图(以行列分别作为两个顶点集V1、V2,当中|V1|=|V2|)
然后把每行x或者每列y看成一个点,而障碍物(x,y)能够看做连接x和y的边。依照这样的思路建图,问题就转化成为选择最少的一些点(x或y)。使得从这些点与全部的边相邻,事实上这就是最小点覆盖问题。
最小点覆盖数 = 最大匹配数
这样本题就转化为求最大匹配数了