最大匹配(1)--poj3041(最大匹配的应用 最大匹配=最小点覆盖数)

                                   A - Asteroids

3 41 11 32 23 2Sample Output
2HintINPUT 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).         这道题题意：给一个N*N的矩阵，有些格子有障碍，要求我们消除这些障碍，问每次消除一行或一列的障碍，
最少要几次。这里将每行x看成一个X结点，每列Y看成一个Y结点，障碍的坐标x,y看成X到Y的
一条边，构建出图后，就变成了找最少的点，使得这些点与所有的边相邻，即最小点覆盖问题。
把每一列当成一个点，每一行当成一个点，若行节点和列节点之间有边，则表明该行列该列有一个障碍物。主要是构图：将每一行当成一个点，构成集合1， 每一列也当成一个点，构成集合2；每一个障碍物的位置坐标将集合1与集合2中的点连接起来，也就是将每一个障碍物作为连接节点的边。这样可以轻易的得出本题是一个最小点覆盖的问题，假设1个行节点覆盖了5个列节点，即这个行节点与这5个列节点间有5条边（即五个障碍物），由于这5条边都被那个行节点覆盖，即表明这5个障碍物都在同一列上，于是可以一颗炸弹全部清除，而本题也就转化成求最小点覆盖数的问题。
又有一个定理是：最小点覆盖数 = 最大匹配数， 所以此题转化成求最大匹配数。
以下是匈牙利算法的代码：
//  main.cpp//  temp////  Created by Sly on 2017/2/21.//  Copyright © 2017年 Sly. All rights reserved.//#include <iostream>#include <stdio.h>#include <string.h>using namespace std;int map[505][505];int link[505];int used[505];int N;bool Find(int x){    int i;    for(i=1;i<=N;i++)    {        if(used[i]==0&&map[x][i]==1)        {            used[i]=1;            if(link[i]==0||Find(link[i]))            {                link[i]=x;                return true;            }        }    }    return false;}int main() {    int K,num;    while(scanf("%d %d",&N,&K)!=EOF)    {        num=0;        int a,b,i;        memset(map,0,sizeof(map));        for(i=0;i<K;i++)        {            scanf("%d %d",&a,&b);            map[a][b]=1;        }        memset(link,0,sizeof(link));        for(i=1;i<=N;i++)        {            memset(used,0,sizeof(used));            if(Find(i))num+=1;        }        cout<<num<<endl;    }    return 0;}