本文主要是介绍KM模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
int Max( int a,int b )
{return a>=b?a:b;
}
bool findpath(int u) //给x[u]找匹配,这个过程和匈牙利匹配是一样的
{visx[u] = 1;for( int v=1; v<=ny; v++ ){if( !visy[v] && lx[u] + ly[v] == map[u][v] ){visy[v] = 1;if( cy[v]==-1 || findpath( cy[v] ) ){cy[v] = u;cx[u] = v;return true;}}}return false;
}
int KM_perfect_match()
{int ans = 0;int slack;memset( cx,-1,sizeof(cx) );memset( cy,-1,sizeof(cy) );memset( lx,0,sizeof(lx) );memset( ly,0,sizeof(ly) );for( int i = 1; i <= nx; i ++ ){for( int j = 1; j <= ny; j ++ ){lx[i] = Max( lx[i],map[i][j] ); //lx[i]为i点权值最大的边}//if( lx[i] == -1 )// return -1; //无法匹配}for( int k = 1; k <= nx; k ++ ) //为x里的每一个点找匹配 不断修改顶标，直到找到完备匹配或完美匹配{while(1){memset( visx,0,sizeof(visx) );memset( visy,0,sizeof(visy) );if( cx[k] == -1 && findpath(k) )break;else //匹配失败，找最小值{slack = inf;for( int i = 1; i <= nx; i ++ ){if( visx[i] ){for( int j = 1; j <= ny; j ++ ){if( !visy[j] && slack > lx[i] + ly[j] - map[i][j] )slack = lx[i] + ly[j] - map[i][j];}}}for( int i = 1; i <= nx; i ++ ){if( visx[i] )lx[i] -= slack;if( visy[i] )ly[i] += slack;}}}}for( int i = 1; i <= nx; i ++ ) //权值相加 ans += map[cy[i]][i]; return ans;
}这篇关于KM模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
