算法基础之二分图的最大匹配

发布时间:2023年12月20日

二分图的最大匹配

  • 核心思想:匈牙利算法 : 寻找有没有可重新连接的路

    • 在这里插入图片描述

    •   #include<iostream>
        #include<cstring>
        #include<algorithm>
        
        using namespace std;
        const int N = 510 , M = 100010;
        
        int h[N],e[M],ne[M],idx;
        int match[N];  //记录与j匹配的i
        int n1,n2,m;
        bool st[N];
        
        void add(int a,int b)
        {
            e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
        }
        
        bool find(int x)  //找能不能连接
        {
                for(int i=h[x];i!=-1;i = ne[i])
                {
                    int j = e[i];
                    if(!st[j])  //这次还没有走过
                    {
                        st[j] = true;  //这次走过了
                        if(match[j] == 0 || find(match[j]))  //没有匹配的 或者 对应x还有备胎能匹配
                        {
                            match[j] = x;  //换一个匹配的
                            return true;
                        }
                    }
                }
                return false;
        }
        
        int main(){
            
            cin>>n1>>n2>>m;
            
            memset(h, -1, sizeof h);
            
            while(m--)
            {
                int a,b;
                cin>>a>>b;
                add(a,b);
            }
            
            int res = 0;
            for(int i = 1;i<=n1;i++)  //遍历每一条边
            {  
                memset(st , false , sizeof st);  //清空状态 否则i=2时可能"知难而退" 不会"追求"
                if(find(i)) res ++ ;  //find是找有无备胎的
            }
            
            cout<<res;
        }
      
文章来源:https://blog.csdn.net/Pisasama/article/details/135096606
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。