一尘不染

所需的最低限度攻击次数

algorithm

我们获得了二维网格单元,每个单元可能包含也可能不包含怪物。

我们将获得包含怪物的单元格列表。

在一次攻击中,我们可以杀死排成一列或一列的所有怪物。我们需要告诉消灭所有怪物所需的最小攻击次数。

限制条件:

1 ≤ N ≤ 1000

1 ≤ X, Y ≤ 10^9

例:

输入:

3

0 0

1 0

0 1

输出:

2

如何解决这个问题。


阅读 189

收藏
2020-07-28

共1个答案

一尘不染

可以将其建模为图问题。

为每个有怪物的行和列创建一个图形节点。如果该行和该列上有怪物,则连接节点。

这是一个二部图,您想要做最小的顶点覆盖。柯尼希定理表明,对于二部图,该问题与最大匹配问题是等价的,可以在政治时间内解决该问题:

http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_graphs

2020-07-28