二分图最大权值匹配算法（KM算法）与匈牙利算法详解

二分图，一种特殊的图结构，将顶点分为两个互不相交的集合，其匹配问题在资源分配中尤为重要。最大匹配目标是尽可能多的配对，而最佳匹配则在带权图中寻找权值之和最大的配对。解决这类问题的关键在于匈牙利算法，其核心是通过寻找增广路，即分配与未分配交替出现的路径，每次找到增广路就更新匹配，直到无增广路，匹配完成。

匈牙利算法的应用涉及深搜和广搜，虽然深搜代码较为简洁，但两者的区别在于数据结构的使用。以图为例，算法过程是：首先用匈牙利算法寻找最大匹配，若无法找到满足条件的完备匹配，就需要通过KM算法更新顶标，继续寻找最佳匹配。这个过程可能需要反复迭代，直到找到最佳匹配的完备匹配。

KM算法是用于解决最佳匹配的，它在完备匹配中寻找满足特定条件的配对，即每个点与另一侧点的权值和相等。通过匈牙利算法找到最大匹配后，用KM算法更新顶标，继续这个递归过程，直至找到最佳匹配。