讲完最大匹配开始讲最大权匹配了。
首先对于所有最大权匹配，可以通过加边加点的方法把问题转化为最大权完备匹配，所以我接下来讲的都是最大权完备匹配而不是最大权匹配。
现在设左边右边都有$n$个点，左边第$i$个点和右边第$j$个点之间边的权值是$w(i,j)$。
先来介绍顶标的概念，顶标就是把整个二分图的每一个点上标一个值，用$labL_i$表示左边第$i$个点的顶标，$labR_j$表示右边第$j$个点的顶标。
那么一组合法的顶标需要满足对于任意一组$(i,j)$有$labL_i+labR_j>=w(i,j)$。也就是说$\sum labL_i+\sum labR_j>=\sum w(i,j)$，于是我们就可以不断调整顶标，使得顶标的和达到最小值，此时$\sum labL_i+\sum labR_j==\sum w(i,j)$，也就是说我们找到了边权和最大的完备匹配。
引用一段话：
設定上限，然後不斷降低上限，降低到極限就碰到最大值了。原本一個求最大值的問題，變成了一個求最小值的問題。這是很實用的數學轉換。
【註：以 Linear Programming 的觀點來看，這個轉換正是 primal problem 與 dual problem 之間的轉換。】
這個轉換有個重要目的：操作 vertex labeling 而不操作 edge labeling ，藉此減少調整權重的時間。
現在只要求出一組總和最小的 vertex labeling ，就得到最大權完美二分匹配。于是接下来就要求出一组总和最小的顶标。
接下来给出等边的定义，等边就是一组$(i,j)$满足$labL_i+labR_j==w(i,j)$的边。
由于二分图最大权完备匹配的最终结果中的匹配边肯定都是等边，那么我们要找的增广路就变成了由等边构成的增广路。
但是如果在当前图中找不到由等边构成的增广路而匹配数没有到$n$时怎么办呢？那就只能通过调整顶标来让图中的等边变多从而找到新的增广路。
那么设$v=min(labL_i+labR_j-w(i,j))$其中$i$是交错路径树中的左边点，$j$是非交错路径树中的右边点。我们让所有交错路径树上的左边点$i$的$labL_i-=v$让所有交错路径树上的右边点$j$的$labR_j+=v$，就可以在保证顶标合法的前提下增加至少一条等边。
如果这个$v$更大的话，顶标就会不合法，如果这个$v$更小的话，就不会增加新的等边，因此每次顶标改变的值都是固定的。
那么接下来简要说一下算法流程(注意我会把$slack$的优化一起说，也就是说我说的是$O(n^3)$的做法)
首先初始化一组合法的顶标，一般是$labL_i=max(w(i,j))$，$labR_j=0$。
然后对于每个左边的点，把他当成起点BFS找增广路。
执行以下步骤直到找到增广路。
那么对于每次队列中队首的左边点$u$，首先让它出队。
然后对于不在交错路径树中的右边点$v$，如果$labL_u+labR_v==w(u,v)$，那么我们找到了一条新的等边。
如果$v$没有匹配点，我们就找到了一条增广路，那么进行增广并结束本次增广路的查找。break;
如果$v$有匹配点，就把$v$的匹配点加入队尾继续寻找增广路。
如果$labL_u+labR_v>=w(u,v)$即$(u,v)$不是等边，就用$labL_u+labR_v-w(u,v)$更新$slack_v$
如果在上述过程中没有找到增广路，那么对于所有不在交错路径树中的$v$，找到$slack_{min}=min(slack_v)$
对于所有在交错路径树中的$u$，$labL_u-=slack_{min}$，对于所有在交错路径树中的$v$，$labR_v+=slack_{min}$
因为$labL$改变了，所以$slack$也会改变，因此对于所有不在交错路径树上的$v$，$slack_v-=slack_{min}$
然后对于所有右边的不在增广路径树中的点$v$，如果$slack_v==0$，那么说明找到了新的等边。
于是设$u$为使$slack_v==0$的左边点，像之前找交错路径树一样讨论：
如果$v$没有匹配点，我们就找到了一条增广路，那么进行增广并结束本次增广路的查找。break;
如果$v$有匹配点，就把$v$的匹配点加入队尾继续寻找增广路。
如果在上述过程中仍没有找到增广路，那么就把现在仍在队列里的点当成起点继续找增广路继续调整顶标。
最后把所有顶标累加就是最大权完备匹配的结果啦~
那么二分图最大权完备匹配就讲完咯
另外欢迎大家来问我和二分图最大权匹配有关的问题
谢谢大家！
鄂公网安备 42010202000505 号