题目链接
方法:二分图
题目分析
题目大意
给出一个$n*n$的图,图中有些小行星,一次可以粉碎一行或者一列上的所有小行星,问如何清理可以使所有小行星都被粉碎。
解析
二分图的题目。
把一个点当成一条边,分别连着两个集合,一个集合表示行一个集合表示列,那么这题就转化为了求最小点覆盖问题。
根据公式,我们知道如下结论:
最小点覆盖 = 最大匹配数
于是无脑的用二分图的模版即可。
代码
1 |
|
Pursue excellence; Strive for perfection.
方法:二分图
给出一个$n*n$的图,图中有些小行星,一次可以粉碎一行或者一列上的所有小行星,问如何清理可以使所有小行星都被粉碎。
二分图的题目。
把一个点当成一条边,分别连着两个集合,一个集合表示行一个集合表示列,那么这题就转化为了求最小点覆盖问题。
根据公式,我们知道如下结论:
最小点覆盖 = 最大匹配数
于是无脑的用二分图的模版即可。
1 | #include <set> |