假设我们现在循环到了第\(i\)个点，且前面\(i-1\)个点都已经被匹配了，现在的相等子图为\(S\)
在\(A_i+\delta,B_i-\delta\)后，相等子图变成了\(S'\)：
对于匹配边，其两端要么都在交错树中要么都不在交错树中，不可能出现一端在一端不在的情况，所以匹配边仍然在\(S'\)中
对于交错树上的边，显然每一条仍然在\(S'\)中
我们不妨假设前面\(i-1\)个点都是直接地找到了匹配边（也就是没有寻找增广路的过程），所以对\(S'\)重新跑一遍匈牙利，前面\(i-1\)个点选的匹配边仍然不变，第\(i\)个点的交错树一定是\(S\)中第\(i\)个点的交错树的超集
假设原图中仍然存在边\((i,j)\)满足\(i∈T,j∉T\)，那么我们肯定就可以找到这么一个最小的\(\delta\)
先来验证在\(A_i+\delta,B_i-\delta\)后，对原图（注意不是\(S\)和\(S'\)，是数据给出的所有边和所有点组成的原图）中的任意一条边仍然满足顶标不等式：如果这条边两端都在交错树或者都不在交错树中，那么仍然满足不等式；如果这条边的右部在交错树中但是左部不在，那么由于右部增加了一个\(\delta\)而左部没变，所以这条边仍然满足不等式；如果这条边的左部在交错树中但是右部不在，由于我们找的\(\delta\)是最小的，所以仍然满足不等式
也就是说如果我们每次都能找到这么一个\(\delta\)，那么构建的新的相等子图\(S'\)一定满足顶标不等式，也就说明P430的定理可以用
那么我们在第\(i\)个点找到增广路之前，一定能够找到这么一个\(\delta\)吗？
是可以的
假设我们已经找不到这么一个\(\delta\)了但是还是没有找到增广路。我们为什么会找不到这么一个\(\delta\)？是因为原图中不存在满足\(i∈T,j∉T\)的边\((i,j)\)了。我们考虑第\(i\)个点，这就说明与其关联的边\((i,j)\)都已经被加入到相等子图中了（否则的话此时第\(i\)个点的交错树就不会包含这条边，因为这条边压根就没有被添加到相等子图中，而交错树的边肯定都是相等子图的边，也就是说原图中存在满足\(i∈T,j∉T\)的边\((i,j)\)）；由于此时我们还没有找到增广路，也就是说对每条与\(i\)关联的边的另一个端点\(j\)都是匹配点（否则\(i->j\)就是一条增广路），考虑每个\(j\)的匹配点\(match_j\)，对每个\(match_j\)来说，与其关联的边\((match_j,k)\)也都已经被加入到相等子图中了（否则的话此时第\(i\)个点的交错树就不会包含这条边，因为这条边压根就没有被添加到相等子图中，而交错树的边肯定都是相等子图的边，也就是说原图中存在满足\(match_j∈T,k∉T\)的边\((match_j,k)\)）；以此类推。然后考虑最终形成的这棵交错树是什么样子的呢？实际上就是我们将原图中所有的边都添加进这个相等子图中，然后第\(i\)个点跑出的交错树（因为与交错树中的左部节点关联的边全部被加入到了相等子图中）。然而，由于原图存在完备匹配，所以如果我们将原图中所有的边都添加进这个相等子图中，第\(i\)个点根本跑不出交错树，矛盾了，所以说明我们在第\(i\)个点找到增广路之前，一定能够找到这么一个\(\delta\)
综上我们能在满足顶标不等式的前提下找到一个带权最大匹配
代码熟悉一下
标签：原图,相等,个点,交错,子图,KM,算法,暂时性,delta From： https://www.cnblogs.com/dingxingdi/p/18225230