链接:hdu3041
Description
- Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <=
- N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice
points of the grid.
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of
- the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the
- location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to
- eliminate all of the asteroids.
Input
- Line 1: Two integers N and K, separated by a single space.
- Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and
- column coordinates of an asteroid, respectively.
Output
- Line 1: The integer representing the minimum number of times Bessie must shoot.
Sample Input
3 4
1 1
1 3
2 2
3 2Sample Output
2题解
- 二分图最小点覆盖
- 其实就等于二分图最大匹配
- 数组忘了清零,WA一发,数组开大十倍,TLE一发
1 |
|