http://acm.hdu.edu.cn/showproblem.php?pid=2063
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int N = 500+10; 6 int gil,boy; 7 int gil_boy[N][N]; 8 int flg[N];//在递归过程中男生N是否有女朋友 9 int bg[N];//男生N的女朋友 10 //匈牙利算法 11 int xfind(int g)//女生g找男朋友 12 { 13 int b;//男生b 14 for(b=1;b<=boy;b++)//找可以匹配的男生 15 { 16 if(gil_boy[g][b]&&!flg[b])//可以匹配并且该男生在这一轮中还没有匹配 17 { 18 flg[b]=1;//匹配 19 if(!bg[b]||xfind(bg[b]))//该男生没有女朋友或者他的女朋友可以再找一个男朋友 20 { 21 bg[b]=g;//女生g找到男朋友b，匹配成功 22 return 1; 23 } 24 } 25 } 26 return 0;//匹配失败 27 } 28 int main() 29 { 30 int i,m,g,b,ans; 31 while(cin>>m&&m) 32 { 33 cin>>gil>>boy;ans=0; 34 memset(gil_boy,0,sizeof(gil_boy)); 35 memset(bg,0,sizeof(bg)); 36 for(i=0;i<m;i++) 37 { 38 scanf("%d%d",&g,&b); 39 gil_boy[g][b]=1; 40 } 41 for(g=1;g<=gil;g++)//每个女生找男朋友 42 { 43 memset(flg,0,sizeof(flg)); 44 if(xfind(g)) ans++;//女生找到男朋友 45 } 46 cout<<ans<<endl; 47 } 48 return 0; 49 }