POJ.3041 Asteroids

· · 题解

给定一个网格，网格上有敌人，每次可以同时消灭某一行或某一列上的所有敌人。求消灭所有敌人需要的最小操作次数。

我们将每个敌人的所在行与所在边连边，问题转化成：

在图中选择最少的点，使得每条边的两个端点中至少有一个被选择。

这是最小点覆盖。而最小点覆盖等于最大匹配，所以直接 dinic 做完了。