小编Sin*_*ina的帖子

我的问题是关于最大权重 B 匹配问题。

二部匹配问题将二部图中的两组顶点配对。甲最大加权匹配二部（MWM）被定义为一个匹配，其中在匹配的边的值的总和有最大值。一个著名的 MWM 多项式时间算法是匈牙利算法。

我感兴趣的是一个特定的最大加权二分匹配，称为权重二分 B 匹配问题。权重二分 B 匹配问题 (WBM) 寻求匹配顶点，以便每个顶点与不超过其容量b允许的顶点匹配。

此图（来自Chen 等人）显示了 WBM 问题。输入图的得分为 2.2，即所有边权重的总和。解决方案 H 的蓝色边缘在满足红色度约束的所有子图中产生最高分，1.6。

尽管最近有一些工作解决了 WBM 问题（this和this），但我找不到该算法的任何实现。有谁知道 WBM 问题是否已经存在于像 networkX 这样的任何库中？