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

布满荆棘的人生 2021-09-17 14:46 267阅读 0赞

[http://imlazy.ycool.com/post.1603708.html][http_imlazy.ycool.com_post.1603708.html]看了这能很好的理解二分图的最大匹配问题。

这题要会把row和col转换成为两个顶点集，(x,y)看成边。问题就转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，其实这就是最小点覆盖问题。在二分图中，**最小点覆盖数=最大匹配数。**所以可以用匈牙利算法解决。

二分图最大匹配的匈牙利算法看了好久，现在终于有点眉目了。加油哟！！

![2012050100392810.png][]

#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;
    }

[http_imlazy.ycool.com_post.1603708.html]: http://imlazy.ycool.com/post.1603708.html
[2012050100392810.png]: /images/20210726/3687dd1d98a0414a8df1470fdcbf73d9.png