我们有一个二维的细胞网格。每个细胞可能包含也可能不包含怪物。
我们得到了包含怪物的单元格列表。
在一次攻击中，我们可以杀死所有排成一排或一列的怪物。我们
需要告诉消灭所有怪物所需的最少攻击次数。
限制条件：
1 ≤ N ≤ 1000
1 ≤ X, Y ≤ 10^9
Example:
Input:
3
0 0
1 0
0 1
Output:
2
如何解决这个问题..？
这可以建模为图形问题。
为有怪物的每一行和每一列创建一个图形节点。
如果该行和该列上有怪物，则连接节点。
这是一个二部图，您想要进行最小顶点覆盖。柯尼希定理 http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29表明对于二部图，该问题等效于可以在多项式时间内解决的最大匹配问题：
http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_graphs http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_graphs
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
