二分图最大权值分配KM算法的伪代码

二分图的最大权值匹配通常采用的是匈牙利算法（Kuhn-Munkres算法，也称为Menger增广路算法），它不是简单的二分搜索，而是通过构建增广路径来逐步找到一个最大权重的配对。以下是 KM 算法的基本伪代码：

function hungarian_algorithm(G):
    // G 是一个二维数组，表示二分图，G[i][j] = w if (i, j)有边，0 otherwise
    n := number_of_nodes
    dist_matrix := initialize_dist_matrix(n)  // 初始化距离矩阵
    matched_pairs := empty_set

    while there exists unmatched nodes:
        augment_path := find_augmenting_path(dist_matrix)
        if augment_path is null:
            # 如果找不到增广路径，说明图已经是最优匹配，结束循环
            break

        for edge in augment_path:
            match edge's endpoints
            update dist_matrix for the edges crossed by the path

    return matched_pairs, total_weight(matched_pairs)

function find_augmenting_path(dist_matrix):
    start_node := find_min(dist_matrix)  // 找到剩余节点中距离最小的一个
    current_path := [start_node]
    while current_path[-1] != null:
        next_node = find_adjacent_with_smaller_distance(current_path[-1], dist_matrix)
        if next_node is not null:
            add next_node to current_path
            relax_edge(current_path[-1], next_node, dist_matrix)
        else:
            return backtrack_to_find_next_path(start_node, current_path)
    return null if at a sink node, otherwise current_path

// 其他辅助函数如initialize_dist_matrix(), relax_edge()等

这个过程会反复寻找并添加增广路径，直到所有节点都有匹配为止。注意每个操作都会更新距离矩阵，以便下一次迭代找出更长的路径。