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

二分图的最大匹配

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

  • 

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