poj 3041 第一题二分图最大匹配-蒲公英云

poj 3041 第一题二分图最大匹配

     [http://imlazy.ycool.com/post.1603708.html][http_imlazy.ycool.com_post.1603708.html]看了这能很好的理解二分图的最大匹配问题。
    这题要会把row和col转换成为两个顶点集，(x,y)看成边。问题就转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，其实这就是最小点覆盖问题。在二分图中，**最小点覆盖数=最大匹配数。**所以可以用匈牙利算法解决。
   二分图最大匹配的匈牙利算法看了好久，现在终于有点眉目了。加油哟！！

#include <iostream>
#include <fstream>
using namespace std;
#define MAXN 501
int N,K;
bool map[MAXN][MAXN],v[MAXN];
int link[MAXN]; 
bool dfs(int x)
{
       int i;
       for(i=1; i<=N; i++)
       {
           if(!v[i] && map[x][i])
           {
               v[i]=true;
               if(link[i]==0 || dfs(link[i]))
               {   
                   link[i]=x;
                   return true;
               }
           }
       }
       return false;
}
int main()
{
    int i,result=0;
    memset(map,false,sizeof(map));
    memset(link,0,sizeof(link));
    freopen("acm.txt","r",stdin);
    scanf("%d%d",&N,&K);
    for(i=1; i<=K; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        map[a][b]=true;
    }
    for(i=1; i<=N; i++)
    {
        memset(v,false,sizeof(v));
        if(dfs(i))
            result++;
    }
    printf("%d\n",result);
    return 0;
}