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