本文主要是介绍Hopcroft-Karp算法模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://blog.csdn.net/u011742541/article/details/14104573
//Hopcroft-Karp算法 有点类似dinic 都是先对图BFS分层再沿层数DFS找增广路
//***************************************************************************
bool searchPath() //BFS 对二分图分层
{ dist = inf; queue<int>que; memset( dx,-1,sizeof(dx) ); memset( dy,-1,sizeof(dy) ); for( int i = 1; i <= nx; i ++ ){ //找到x集合所有未被匹配的点压入队列中 if( cx[i] == -1 ){ que.push(i); dx[i] = 0; } } while( !que.empty() ){ int u = que.front(); que.pop(); if( dx[u] > dist ) //只分层到第一个找个的可匹配点层数 break; for( int v = 1; v <= ny; v ++ ) { if( map[u][v] && dy[v] == -1 ){ dy[v] = dx[u] + 1; if( cy[v] == -1 ) //找个一个可以匹配点 标记分层的层数 dist = dy[v]; else{ dx[cy[v]] = dy[v] + 1; que.push( cy[v] ); } } } } return dist != inf;
}
bool findPath( int u ) //沿着层数DFS
{ for( int v = 1; v <= ny; v ++ ){ if( map[u][v] && !vis[v] && dy[v] == dx[u] + 1 ){ vis[v] = true; if( cy[v] != -1 && dy[v] == dist ) //如果v已经有匹配了且v的层数为dist（ 最大层数为dist 所以v原来匹配的不可能再匹配 ） continue; if( cy[v] == -1 || findPath( cy[v] ) ){ //如果v未匹配就跟u匹配v 否则看v原来匹配的是否还能跟其他的匹配 能就跟u匹配 不能就不匹配 cy[v] = u; cx[u] = v; return true; } } } return false;
}
int HK_MaxMatch()
{ int ans = 0; memset( cx,-1,sizeof(cx) ); memset( cy,-1,sizeof(cy) ); while( searchPath() ){ //分层 + 判断是否还有未匹配点 memset( vis,0,sizeof(vis) ); for( int i = 1; i <= nx; i ++ ){ if( cx[i] == -1 ) ans += findPath(i); } } return ans;
}
//*************************************************************************** 这篇关于Hopcroft-Karp算法模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
