让G（U U V，E）是一个加权有向二分图（即U和V是两个集的二分图的节点和E包含向加权边从u到v或从v到u）。下面是一个例子：

Let G (U u V, E) be a weighted directed bipartite graph (i.e. U and V are the two sets of nodes of the bipartite graph and E contains directed weighted edges from U to V or from V to U). Here is an example:

在这种情况下：

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)} 

定义： DirectionalMatching 的（我做了这个词只是为了让事情更清晰）：一组有向边是可以共享的开始或结束顶点。也就是说，如果U-> V和U' - > V'同属一个的 DirectionalMatching 的那么V / = U'和V'/ = U，但它可能是U = U'或V = V'。

Definition: DirectionalMatching (I made up this term just to make things clearer): set of directed edges that may share the start or end vertices. That is, if U->V and U'->V' both belong to a DirectionalMatching then V /= U' and V' /= U but it may be that U = U' or V = V'.

我的问题：如何有效地找到的 DirectionalMatching 的，按上述定义，其中最大的边缘的权重之和的二分定向加权图？

My question: How to efficiently find a DirectionalMatching, as defined above, for a bipartite directional weighted graph which maximizes the sum of the weights of its edges?

到有效的，我的意思是多项式复杂或更快，我已经知道如何实现一个幼稚的蛮力方法。

By efficiently, I mean polynomial complexity or faster, I already know how to implement a naive brute force approach.

在上述权重最大的例子中的 DirectionalMatching 的是：{F-> A，C-> E，B-> D}，有一个值13

In the example above the maximum weighted DirectionalMatching is: {F->A,C->E,B->D}, with a value of 13.

正式证明此问题的等价于图论任何其它公知的问题也将是有价值的。

Formally demonstrating the equivalence of this problem to any other well known problem in graph theory would also be valuable.

谢谢！

注意1：这个问题是基于Maximum加权二分匹配_with_向边的但与额外松弛它被允许边缘在匹配共享的来源或目标位置。自那松弛，使一个很大的区别，我创建了一个独立的问题。

Note 1: This question is based on Maximum weighted bipartite matching _with_ directed edges but with the extra relaxation that it is allowed for edges in the matching to share the origin or destination. Since that relaxation makes a big difference, I created an independent question.

注意2：这是一个最大的重量匹配。基数（多少边缘是present）和所涉及的匹配顶点的数目是无关一个正确的结果。只有最大重量事项

Note 2: This is a maximum weight matching. Cardinality (how many edges are present) and the number of vertices covered by the matching is irrelevant for a correct result. Only the maximum weight matters.

注意2：在我的研究来解决，我发现本文中的问题，我认为这将是帮助他人试图找到一个解决方案：的