本文主要是介绍KM最小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu1853
const int inf = 1000000000 ;const int maxn = 508 ;
bool sx[maxn], sy[maxn] ;
int match[maxn], w[maxn][maxn] ;
int n , m , lx[maxn] , ly[maxn] ;
//n：左集元素个数； m：右集元素个数
void init (){memset(w , 0 , sizeof(w)) ; //不一定要，求最小值一般要初始化为负无穷！
}int dfs(int u){sx[u] = 1 ;for(int v = 0 ; v < m ; v++){if(!sy[v] && lx[u] + ly[v] == w[u][v]){sy[v] = 1 ;if(match[v] == -1 || dfs(match[v])){match[v] = u;return 1 ;}}}return 0 ;
}int KM(){int i , j , k ;memset(ly , 0 , sizeof(ly));for(i = 0 ; i < n ; i++){lx[i] = -inf ;for(j = 0; j < m; j++) lx[i] = max(lx[i] , w[i][j]) ;}memset(match , -1 , sizeof(match)) ;for(i = 0 ; i < n ; i++){while(1){memset(sx , 0 , sizeof(sx)) ;memset(sy , 0 , sizeof(sy)) ;if(dfs(i)) break ;int d = inf;for(j = 0 ; j < n ; j++){if(sx[j]){for(k = 0; k < m; k++)if(!sy[k]) d = min(d , lx[j]+ly[k]-w[j][k]) ;}}if(d == inf) //找不到完美匹配return -1 ;for(j = 0 ; j < n ; j++){if(sx[j]) lx[j] -= d ;}for(j = 0 ; j < m ; j++){if(sy[j]) ly[j] += d ;}}}int sum = 0 , cnt = 0 ;for(i = 0 ; i < m ; i++){if(match[i] > -1 && w[match[i]][i] != -inf){sum += w[match[i]][i];cnt++ ;}}if(cnt != n) return -1 ;return sum;
}int main(){int t , u , v , c ;while(cin>>n>>t){m = n ;for(int i = 0 ; i < n ; i++)for(int j = 0 ; j < m ; j++) w[i][j] = -inf ;for(int i = 0 ; i < t ; i++){scanf("%d%d%d" , &u , &v , &c) ;u-- , v-- ;if(w[u][v] < -c) w[u][v] = -c ;}int s = KM() ;printf("%d\n" , s == -1 ? -1 : -s) ;}return 0 ;
}这篇关于KM最小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
