問題可以轉(zhuǎn)換為最小點集覆蓋問題，既求二分圖的最大匹配。
1 #include <stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 int N=0;
5 int K=0;
6 int R=0;
7 int C=0;
8 int asteroids[501][501];
9 int mark[501],match[501];
10 int FindPath(int x){
11 int tmp=0;
12 for (int i=1;i<=N ;i++ )
13 {
14 if(asteroids[x][i] && !mark[i]){
15 mark[i]=1;
16 if(match[i]==0 || FindPath(match[i])){
17 match[i]=x;
18 return 1;
19 }
20 }
21
22 }
23 return 0;
24 }
25 int main()
26 {
27 scanf("%d %d",&N,&K);
28 memset(asteroids,0,sizeof(asteroids));
29 for (int i=1;i<=K ;i++ )
30 {
31 int row,column;
32 scanf("%d %d",&row,&column);
33 asteroids[row][column]=1;
34 }
35 int count=0;
36 memset(match,0,sizeof(match));
37 for (int i=1;i<=N ;i++ )
38 {
39 memset(mark,0,sizeof(mark));
40 if (FindPath(i)) count++;
41 }
42 printf("%d\n",count);
43 }