关于最小权匹配

考虑两个大小为$n$的点集$I$和$J$，两个集合之间有一完全二分图，边$\left<i,j\right>$具有边权$c[i][j]$。下文中所有$i$都是指$I$中的点，$j$都是指的$J$中的点。

最小权匹配首先就有一个算法是KM算法，其思路如下：考虑求一组点权$u[i]$以及$v[j]$满足：

$$u[i]+v[j]\leq c[i][j],$$ 并且对于满足$u[i]+v[j]=c[i][j]$的边构成的子图，要存在一个完美匹配。
KM的调整$u$和$v$的做法是：每一次选择一个未匹配的$i^*$，搜索出从其出发走交错路能到达的所有点构成的集合$Z$。这里的交错路必须只走$u[i]+v[j]=c[i][j]$的边。于是有两种可能，一种是出现了一条增广路，那么这意味着可以直接增广，使得匹配量加一，另一种可能是没有增广路，那么$|Z\cap I|=|Z\cap J|+1$，这时取$\mu:=\min\{c[i][j]-u[i]-v[j]\mid i\in Z\cap I,j\in J\setminus Z\}$，并将$Z\cap I$中的$u[i]$全都加上$\mu$，将$Z\cap J$中的$v[j]$全都减去$\mu$，然后重新从$i^*$出发找新的$Z$。
总计会从$n$个$i^*$出发试图增广，每次增广最多触发$n$次改值（因为每次该值之后，$Z\cap J$一定是增大的，注意有些博客说满足$u[i]+v[j]=c[i][j]$的边数一定增多，这并不一定，因为该值之后，$I\setminus Z$和$Z\cap J$之间的边可能从满足等式变成小于），而每次改值会有至多$2n$个点要改值，故总计$O(n^3)$个点要改值。但是，每次求$Z$的过程可能会花费$O(n^2)$的时间，所以直接这么裸写，会导致时间复杂度为$O(n^4)$。网传这个算法有办法优化到$O(n^3)$，但是我实在没找到，但是我找到另一篇论文，不排除网传的“$O(n^3)$版KM”就是指这个的可能性。但我个人人为下一段所说的算法中有个细节差别太大了。

现在依旧考虑是要求出一组点权$u[i]$以及$v[j]$满足$u[i]+v[j]\leq c[i][j]$，且$u[i]+v[j]=c[i][j]$的边构成的子图要有完美匹配。
LAPJV的做法是：每次选择一个未匹配的$i^*$，按照$c[i][j]-u[i]-v[j]$作为长度（这说明这次不限制只走$u[i]+v[j]=c[i][j]$的边），只走交错路，运行狄克斯特拉，求出最短增广路，长度设为$\mu$，并且顺带存下求出最短增广路之前$i^*$到所有$k\in J$的距离$d[k]$（就是说，如果$d[k]\geq\mu$，则$d[k]$在之后不会再用到）。接着，开始改点权以及增广：将所有$d[k]<\mu$的$J$中点的$v[k]$分别减掉$\mu-d[k]$，这个操作不会导致$c[i][j]-u[i]-v[j]<0$，但可能导致已经匹配的边不再满足相等性。接着，沿着最短增广路增广，得到新的匹配，再接着，由于此时新匹配不一定每条边都满足相等性，那就把所有匹配边上的$i$的$u[i]$增大到让匹配边满足相等性为止。请自行证明这样增加$u[i]$之后，$c[i][j]-u[i]-v[j]\geq0$不会被破坏。于是一共执行$O(n)$次增广，每次增广消耗$O(n^2)$运行狄克斯特拉，并消耗$O(n)$改点权，总计$O(n^3)$。