题意：

假如你如今正处在一个N*N的矩阵中,这个矩阵里面有K个障碍物,你拥有一把武器,一发弹药一次能消灭一行或一列的障碍物,求最小的弹药消灭所有障碍物

输入为:     N K

接下来有K行,每行包括障碍物的坐标,即r行c列;

如:

3 4 

1 1

1 3

2 2

3 2 

输出为:     花费最小的弹药数

思路：将i行作为X集合。将j列作为Y集合。这样原来的问题—用最少的炮弹打掉所有障碍物，转化为了这么一个问题：

在二分图中选择尽量少的点，使得每条边至少有一个端点被选中

裸的最小点覆盖问题，运用结论：最小覆盖数等于最大匹配数  就可以

代码例如以下：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 600;int n, k;bool lin[N][N];int used[N], arr[N];bool find(int x){	for(int j = 1; j <= n; j++)	{		if(lin[x][j] == true && used[j] == 0)		{			used[j] = 1;			if(arr[j] == 0 || find(arr[j]))			{				arr[j] = x;				return true;			}		}	}	return false;}int main(){	int r, c;	while(~scanf("%d%d", &n, &k))	{		memset(lin, false , sizeof(lin));		memset(arr, 0, sizeof(arr));		for(int i = 1; i <= k; i++)		{			scanf("%d%d", &r, &c);			lin[r][c] = true;		}		int all = 0;		for(int i = 1; i <= n; i++)		{			memset(used, 0, sizeof(used));			if(find(i))				all++;		}		printf("%d\n", all);	}	return 0;}