匈牙利算法-找舞伴

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
int uN, vN;            // u,ｖ数目，u为男生数量，v为女生数量
bool g[MAXN][MAXN];        // g[i][j] 表示 xi与yj相连，相连表示可以和对方约会
int xM[MAXN], yM[MAXN];       //   输出量,记录男女生约会的对象，-1表示还没有约会对象
bool chk[MAXN];       // 辅助量 检查某轮 y[v]是否被check 
bool SearchPath(int u){      
	int v;      
	for(v = 0; v < vN; v++) {          
		if(g[u][v] && !chk[v]){    //如果女生愿意和该男生约会，并且这次遍历时还没人找过她（chk[v]用来防止因为查找增广路径递归时，走回头路，即原来的男伴又傻乎乎的找该女生）         
			chk[v] = true;              
			if(yM[v] == -1 || SearchPath(yM[v]))  //如果该女生现在还没有约会对象，或者看看已约她的男生是否能找到其它约会女生（通过查找增广路径）             
			{                 
				yM[v] = u;                        //标记该女生被哪个男生约走
				xM[u] = v;                        //标记该男生约了哪个女生
				return true ;					  //顺利解决该男生的约会对象，返回
			}         
		}     
	}     
	return false ;								//程序到这里，表示这个男生要单身了
}
int MaxMatch(){      
	int u;      
	int ret = 0 ;      
	memset(xM, -1, sizeof (xM));      
	memset(yM, -1, sizeof (yM));      
	for(u = 0; u < uN; u++)      
	{          
		if(xM[u] == -1)							//-1表示该男生还没有约到人
		{              
			memset(chk, false, sizeof (chk));   //给所有女生一次重新选择的机会         
			if(SearchPath(u)) ret++;			//又成了一对
		}     
	}     
	return ret;
}