Asteroids

Description
有K个小行星分布在一个N×N的网格中。有一种武器一次攻击可以将一行或者一列的行星全部消灭。求最少需要多少次攻击才能将K个小行星全部消灭。1≤N≤500 1≤K≤10000

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 2

INPUT DETAILS:
The following diagram represents the data, where "X" is an
asteroid and "." is empty space:
X.X
.X.
.X.
Sample Output
2
OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and
(1,3), and then she may fire down column 2 to destroy the asteroids
at (2,2) and (3,2).

sol:二分图最小点覆盖
对于每一个小行星，要么被这一行的武器攻击，要么被这一列的武器攻击。
现在，我们以行号作为上面的点，列号作为下面的点，某行某列有小行星作为边，来建立二分图。
要使用最少的武器来攻击到所有小行星，即小行星所在的行和列至少一个点被选到，即求最小点覆盖。下图中红色边为匹配边，蓝色圈起来的点为覆盖点。

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int n,m,ans;
 6 int pre[505];
 7 bool v[505],map[505][505];
 8 bool find(int x)
 9 {
10     for(int i=1;i<=n;i++)
11     {
12         if(map[x][i]&&!v[i])
13         {
14             v[i]=true;
15             if(pre[i]==-1||find(pre[i]))
16             {
17                 pre[i]=x;
18                 return true;
19             }
20         }
21     }
22     return false;
23 }
24 int main()
25 {
26     int x,y;
27     scanf("%d%d",&n,&m);
28     memset(map,0,sizeof(map));
29     for(int i=1;i<=m;i++)
30     {
31         scanf("%d%d",&x,&y);
32         map[x][y]=1;
33     }
34     ans=0;
35     memset(pre,-1,sizeof(pre));
36     for(int i=1;i<=n;i++)
37     {
38         memset(v,0,sizeof(v));
39         if(find(i)) ans++;
40     }
41     printf("%d\n",ans);
42     return 0;
43 }

Asteroids

原文：https://www.cnblogs.com/cutepota/p/12839466.html