题目背景

二分图

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

 

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

 

输出格式：

 

共一行，二分图最大匹配

 

输入输出样例

输入样例#1：

1 1 11 1

输出样例#1：

1

说明

n,m<=1000，1<=u<=n，1<=v<=m

因为数据有坑，可能会遇到v>m的情况。请把v>m的数据自觉过滤掉。

算法：二分图匹配

思路：

把1~n中点一个个在保证有所匹配的情况尝试加入。

代码实现：

1 #include
     
       2 #include
      
        3 int n,m,k,ans; 4 int a,b,c; 5 int cp[1010]; 6 bool v[1010]; 7 int h[1010],hs; 8 struct edge{
   int s,n;}e[1000010]; 9 bool Hungarian_algorithm(int k){10     for(int i=h[k];i;i=e[i].n) if(!v[e[i].s]){11         v[e[i].s]=1;12         if(!cp[e[i].s]||Hungarian_algorithm(cp[e[i].s])){13             cp[e[i].s]=k;14             return true;15         }16     }17     return false;18 }19 int main(){20     scanf("%d%d%d",&n,&m,&k);21     for(int i=1;i<=k;i++){22         scanf("%d%d",&a,&b);23         if(a>0&&a<=n&&b>0&&b<=m)24         e[++hs]=(edge){b,h[a]},h[a]=hs;25     }26     for(int i=1;i<=n;i++){27         memset(v,0,sizeof(v));28         if(Hungarian_algorithm(i)) ans++;29     }30     printf("%d\n",ans);31     return 0;32 }
      
     

1 #include
      
        2 #include
       
         3 int n,m,k,ans; 4 int a,b,c; 5 int cp[1010]; 6 bool v[1010]; 7 int h[1010],hs; 8 struct edge{
    int s,n;}e[1000010]; 9 bool Hungarian_algorithm(int k){10     for(int i=h[k];i;i=e[i].n) if(!v[e[i].s]){11         v[e[i].s]=1;12         if(!cp[e[i].s]||Hungarian_algorithm(cp[e[i].s])){13             cp[e[i].s]=k;14             return true;15         }16     }17     return false;18 }19 int main(){20     scanf("%d%d%d",&n,&m,&k);21     for(int i=1;i<=k;i++){22         scanf("%d%d",&a,&b);23         if(a>0&&a<=n&&b>0&&b<=m)24         e[++hs]=(edge){b,h[a]},h[a]=hs;25     }26     for(int i=1;i<=n;i++){27         memset(v,0,sizeof(v));28         if(Hungarian_algorithm(i)) ans++;29     }30     printf("%d\n",ans);31     return 0;32 }
       
      

题目来源：洛谷