POJ-3041 Asteroids
试题链接/problem?id=3041
这个题主要运用了匈牙利算法，在这里强推一篇匈牙利算法趣味精解帖子！（主要是也给自己留一个记录哈哈哈）
**趣写算法系列之–匈牙利算法：**/dark_scope/article/details/8880547#commentBox
匈牙利算法
匈牙利算法的精解乖乖去看大佬的帖子，我在下面记录拓充一下模板，顺便多给一些模板解释。
模板代码：
//匈牙利算法主要是针对两种事物之间的关系以及这两种事物之间的匹配//前期定义的变量const int MAXN = 505;int mm[MAXN][MAXN];//mm用来记录两种事物的中各个点的联系int girl[MAXN];//这里的数组变量名girl主要取自大佬那篇帖子的样例说明，用来记录一种事物当前已经匹配的另一种事物的序号int vis[MAXN];//vis用来记录这种事物在进行匹配时已经访问了另外一种事物中的点的集合int n,m, ans=0;//n为男生数，m为女生数，下题中行列数相等，所以findp内和main内均为n//主要find函数bool findp(int x){//传入的为男生编号for(int j=1;j<=m;j++){//从第一个女生开始遍历，看看每一个女孩跟这个男生有没有暧昧if(mm[x][j]==1 && vis[j]==0){//如果暧昧并且这个女生还没被观察过vis[j] = 1;//先标明这个女生被观察过了if(girl[j]==0 || findp(girl[j])){//这个女孩还牵手成功，或者这个女孩的目前牵手对象可以换一个女生牵手成功，让这个女生和当前这个男生牵手girl[j] = x;//女生的牵手成功对象变成这个男生return true;//牵手成功当然true}}}return false;}//主函数内的部分int main(){//输入两种事物各自分别拥有的点数，在帖子中即为男生数量和女生数量，在下图中为行数和列数，并且输入哪个女生和哪个男生存在关系，即对mm数组进行赋值for(int i=1;i<=n;i++){//针对两种事物中的一种进行遍历，如从男生角度出发，遍历男生对每个男生进行安排memset(vis, 0, sizeof(vis)); //每次都要初始化vis这个数组，因为对于每个男生来说，他要访问每个女生，来判断自己跟这个女生有没有可能if(findp(i)){//如果找到那么一个女孩子与自己匹配，则牵手成功ans++;//成功对数加1}}cout<<ans<<endl;return 0;}
POJ-3041 Asteroids：
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.
（Bessie希望通过一个N x N网格（1 <= N <= 500）形状的危险小行星场导航她的宇宙飞船。网格包含K个小行星（1 <= K <= 10,000），它们方便地位于网格的格点处。
幸运的是，Bessie拥有一种强大的武器，可以通过一次射击在网格的任何给定行或列中蒸发所有小行星。这种武器非常昂贵，所以她希望谨慎使用它。给出所有小行星的位置。现场，找到Bessie需要射击以消灭所有小行星的最小射击次数。）
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.
（第1行：两个整数N和K，由一个空格分隔。
行2…K + 1：每行包含两个空格分隔的整数R和C（1 <= R，C <= N），分别表示小行星的行和列坐标。）
Output（输出格式）：
*Line 1: The integer representing the minimum number of times Bessie must shoot.
（第1行：表示贝茜必须拍摄的最小次数的整数。）
Sample Input（输入样例）：
3 4
1 1
1 3
2 2
3 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).
（下图表示数据，其中“X”是小行星，“。” 是空的空间：
XX
.X。
。X。
Bessie可以在第1排射击以消灭（1,1）和（1,3）处的小行星，然后她可以向下射击第2列以摧毁（2,2）和（3,2）处的小行星。）
大致思路：思路就是匈牙利算法思路，这里呢就可以把模板例子中的男孩女孩换成行列思考，他这里是消除的时候是按整行的那种消除，所以啊，就思考一边，就站在行的方面思考就可以直接套用模板了，只要能看懂匈牙利算法，就能快速解题。
具体代码如下：
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int MAXN = 505;int mm[MAXN][MAXN];int cc[MAXN];int vis[MAXN];int n, k, ans=0;bool findp(int x){for(int j=1;j<=n;j++){if(mm[x][j]==1 && vis[j]==0){vis[j] = 1;if(cc[j]==0 || findp(cc[j])){cc[j] = x;return 1;}}}return 0;}int main(){cin>>n>>k;for(int i=0;i<k;i++){int r, c;cin>>r>>c;mm[r][c] = 1;}for(int i=1;i<=n;i++){memset(vis, 0, sizeof(vis));if(findp(i)){ans++;}}cout<<ans<<endl;return 0;}
准备省赛，继续坚持！一起加油！
