题意：

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

输入为:     N K

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

如:

3 4 

1 1

1 3

2 2

3 2

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

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

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

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

代码例如以下：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

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;

}