我知道各种算法来计算加权的、无向的二分图的最大加权匹配（即分配问题）：
例如。。。匈牙利算法、Bellman-Ford甚至Blossom算法（适用于一般图，即非二分图）。
然而，如果二分图的边是加权和有向的，我如何计算最大加权匹配？
我很喜欢指向具有多项式复杂性的算法或先前使图无向的转换，这样我就可以应用上述任何算法。
编辑：请注意，匹配应该最大化边的权重，这就是为什么具有定向边会产生差异（a->B可以具有与B->a完全不同的权重）。
诚然，如果我最大化基数，有向边不会有什么不同，我可以应用任何著名的算法来最大化基数：Hopcroft–Karp，最大网络流量。。。。
编辑2：由于匹配是一个通常适用于无向图的术语，让我澄清一下我在这个问题中所说的与匹配的确切含义：一组不共享起始顶点或结束顶点的有向边。更正式地说，如果U->V和U'->V'是匹配的一部分，那么V/=U'和V'/=U。
dfb的注释是正确的，对于任何两个顶点A，B，您可以丢弃两条边AB和BA中较便宜的一条。
证据只有一句：
定理：对于任意两个顶点A，B，最大匹配M从不包含AB和BA的廉价边。
证明：设M为最大匹配。假设AB在M中并且比BA便宜。定义M'=M-{AB}+{BA}。M'显然仍然是一个匹配，但它更贵。这反驳了M是最大匹配的假设。