本文共 2381 字，大约阅读时间需要 7 分钟。

Asteroids

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 26878		Accepted: 14471

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 41 11 32 23 2

Sample Output

2

Hint

INPUT DETAILS: 

The following diagram represents the data, where "X" is an asteroid and "." is empty space:  X.X  .X.  .X.  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).

Source

思路：

将每行、每列分别看作一个点，对于case的每一个行星坐标（x，y），将第x行和第y列连接起来，例如对于输入：

（1，1）、（1，3）、（2，2）、（3，2）4点构造图G：

这样，每个点就相当于图G的一条边，消灭所有点=消灭图G的所有边，又要求代价最少，即找到图G上的最少的点使得这些点覆盖了所有边。

根据定理吗， 最小点覆盖数=最大匹配数，所以本题转化为二分图的最大匹配问题——用匈牙利算法来解决。

推荐一个好的讲解匈牙利算法的博文：

代码：

#include
   
    #include
    
     #include
     
      using namespace std; int n, k;int v1, v2;//二分图顶点集，都等于nbool map[501][501];bool visit[501]; //记录v2中的每个点是否被搜索过int link[501]; //记录v2中的点y在v1中所匹配的点x的编号  int result;//最大匹配数  bool dfs(int x){	for (int y = 1; y <= v2; y++)	{		if (map[x][y] && !visit[y])		{			visit[y] = true;			if (link[y] == 0 || dfs(link[y]))			{				link[y] = x;				return true;			}		}	}	return false;} //匈牙利算法hungary algorithmvoid search(){	for (int x = 1; x <= v1; x++)	{		memset(visit,false,sizeof(visit));		if (dfs(x)) //从v1中的节点x开始寻找增广路径p			result++;	}} int main(){	//ifstream in("input.txt");	cin >> n >> k;	v1 = v2 = n;	int x, y;	memset(map,0,sizeof(map));	for (int i = 1; i <= k; i++)	{		cin >> x >> y;		map[x][y] = true;	}	search();	cout << result << endl;	//system("pause");	return 0;}
     
    
   

 

转载地址：https://joycez.blog.csdn.net/article/details/83051445 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！