请详细描述如何应用KM算法求解带权二分图的最大完美匹配，并介绍如何通过引入松弛量优化算法效率。

在图论中，KM算法是一种经典的算法，用于解决二分图的最大权重完美匹配问题。KM算法的核心在于通过预设可行顶标，使用匈牙利算法找到相等子图的最大匹配，并通过顶标更新过程逐步找到最优匹配。整个过程可以分为以下几个步骤：

参考资源链接：[KM算法详解：解决二分图最优匹配问题](https://wenku.csdn.net/doc/645d940495996c03ac4359ef?spm=1055.2569.3001.10343)

1. 初始化：首先，为二分图的两个顶点集X和Y的每个顶点预设顶标，初始顶标可以任意设定，但需要满足顶标之和大于等于与之相连边的权值。

2. 匈牙利算法：使用匈牙利算法在当前相等子图中寻找最大匹配。如果没有找到完美匹配，则进行顶标更新。

3. 顶标更新：如果当前没有完美匹配，需要调整顶标以扩大相等子图的大小。这通常通过寻找未匹配顶点集X中顶标和与之相连边的权值之间的最小差值，更新顶标，使得调整后的顶标和大于等于对应边的权值。

4. 松弛量优化：在顶标更新过程中引入松弛量，松弛量指的是顶标与边权值之间的差值。通过合理利用松弛量，可以更快地判断顶标更新的方向和幅度，从而提高算法效率。松弛量的引入可以在顶标更新的计算过程中减少不必要的重复计算，显著提升算法性能。

5. 检查完美匹配：更新顶标后，再次使用匈牙利算法寻找最大匹配。如果找到完美匹配，则算法结束；否则继续调整顶标。

6. 结果输出：最终，当算法找到完美匹配时，输出匹配结果，并计算所有匹配边的权值总和，即为最大权重和。

KM算法的时间复杂度主要受顶标更新过程的影响。原始算法的时间复杂度为O(n^4)，通过优化顶标更新过程，并合理使用松弛量，可以将复杂度降低到O(n^3)或更优。

为了更深入理解和应用KM算法，推荐参考《KM算法详解：解决二分图最优匹配问题》一书。该书详细解释了KM算法的原理，并通过实例展示了算法的应用和优化过程，是学习和掌握KM算法的宝贵资源。

参考资源链接：[KM算法详解：解决二分图最优匹配问题](https://wenku.csdn.net/doc/645d940495996c03ac4359ef?spm=1055.2569.3001.10343)