与有向边的最大加权二分匹配

我知道计算最大加权匹配的各种算法加权、无向二分图（即分配问题）：

例如......匈牙利算法、贝尔曼-福特算法甚至 Blossom 算法（适用于一般图，即非二分图）。

但是，如果二分图的边是，如何计算最大加权匹配加权和定向?

我希望能够提供具有多项式复杂度的算法或先前变换的指针，以使图形无向，以便我可以应用上述任何算法。

Edit:请注意，匹配应该最大化边的权重，这就是为什么有向边会产生影响（A->B 可以具有与 B->A 完全不同的权重）。

诚然，如果我最大化基数，有向边不会产生影响，我可以应用任何众所周知的算法来最大化基数：Hopcroft–Karp、最大网络流......

Edit 2: Since matching是一个通常应用于无向图的术语，让我澄清一下我的确切含义matching在这个问题中：一组不共享起始或结束顶点的有向边。更正式地说，如果 U->V 和 U'->V' 是匹配的一部分，则 V /= U' 且 V' /= U。

dfb的评论是正确的，对于任意两个顶点A，B，您可以丢弃两条边AB和BA中更便宜的一条。

证明是一句话：

Theorem:对于任意两个顶点 A,B，最大匹配 M 永远不会包含 AB 和 BA 中较便宜的边。

Proof:设M为最大匹配。假设AB在M并且比BA便宜。定义 M' = M - {AB} + {BA}。 M'显然仍然是一个匹配，但它更贵。这与 M 是最大匹配的假设相矛盾。