二分图带权最大匹配

关于二分图：二分图及染色法判定-CSDN博客

关于二分图最大匹配：二分图最大匹配——匈牙利算法详解

红娘刚给上一批男女牵完线，便又遇到了3对男女（即3男3女），这次虽然比之前人少但也没那么好对付，每个男生都对若干个女生都有意思，每个女生也都对若干个男生都有意思，但是每对男女间的好感度不同，固然可以很容易配成3对情侣，但很难让每个人都满意，所以他们来请红娘出出主意。

红娘了解了每对男女间的好感度后思索了一会便有了主意，她找来三个男生要求他们根据对三个女生亲密度给出对理想对象的期望值，要求给出的期望值不得小于其对任何一个女生的亲密度，女生那边则先不给出期望值。三个男生有些不好意思，便都只给出了和三个女生中的最大亲密度为期望值，于是又有了这样一张图：

红娘打的什么算盘呢？她要让每个人都能有对象的情况下使得最终配对的情侣的亲密度之和最大，这是尽可能使每个人都满意的最好结局了。她要让最终每对情侣的期望值之和都等于其亲密值。

得到了男生们给出的期望值后，她先去给期望值之和恰好等于亲密度的男女配对（红线代表配对），男一和女三成功牵线：

到了男二，发现符合条件的只有女三（期望值之和为亲密度），但是女三已经配对了，于是红娘让男一男二期望值都降低1，女三期望值提高1，如此一来男一女三仍符合条件，男二和女一也符合条件了，于是男儿女一牵线成功：

现在只剩男三落单了，对于她而言，只有女三有好感，但是二者期望值不符合条件，于是红娘先让男三降低1期望值：

接着让男一、男二、男三都降低1期望值，女一、女三都提高1期望值，这样男一和女一符合条件可以配对，男二和女二符合条件可以配对，男三和女三符合条件可以配对：

这样一来大家都有了归宿，且配对的男女的期望值之和恰为亲密度。显然，这是大家最满意的结局。

给定一张二分图，二分图的每条边都带有一个权值。求出该二分图的一组最大匹配，使得匹配边的权值总和最大。这个问题称为二分图的带权最大匹配，也称二分图最优匹配。注意，二分图带权最大匹配的前提是匹配数最大，然后再最大化匹配边的权值总和。

如果一个二分图的带权最大匹配还是一个完备匹配，那么我们称其为二分图带权最大完备匹配，如引例”红娘再牵线“就是一个二分图带权最大完备匹配的例子。

二分图带权最大完备匹配是二分图带权最大匹配的子问题，能解决二分图带权最大匹配自然能解决二分图带权最大完备匹配。

对于二分图带权最大匹配我们通用方法是费用流，其自然也可以解决二分图带权最大完备匹配，也是我们最常用的方法，当然，对于二分图带权最大完备匹配有一专门解决方法——KM算法。

KM算法是对匈牙利算法的改造，我们从匈牙利算法入手，分析如何改造得以求解二分图带权最大完备匹配问题。

在匈牙利算法中，如果从某个左部节点出发寻找匹配失败，那么在DFS的过程中，所有访问过的节点，以及为了访问这些节点而经过的边，共同构成一棵树。

这棵树的根是一个左部节点，所有叶子节点也都是左部节点(因为最终匹配失败了)，并且树上第1，3，5，… 层的边都是非匹配边，第2，4，6，…层的边都是匹配边。因此，这棵树被称为交错树。

亦即”顶点标记值“，在二分图中，给第i(1