algorithm - 加权顶点的最大权重二分匹配

Question

我有一个带有两组顶点 A 和 B 的二部图。边没有权重。但是，其中一个集合（比如集合 B）中的顶点具有分配给它们的正权重（wb1，wb2 ...）我想在这个二分图中找到一个匹配，以便最大化从集合匹配的顶点的权重B.

经过广泛的在线搜索，这就是我想出的：将权重 wbi 分配给顶点 bi 上的所有边缘并运行匈牙利算法。有没有更有效的方法来看待这个问题，因为它不同于加权最大匹配（这里顶点具有权重而不是边）

如果我的语言不清楚，请随时编辑。谢谢你。

Answer 1

如果从 O(V^3) 到 O(VE) 的改进和更简单的算法是值得的（对于最密集的图来说不是渐近的），您可以利用匹配的拟阵结构，如下所示。通过反复选择通往 B 中权重尽可能大的不匹配顶点的路径来实例化Ford-Fulkerson 。