覆盖一个分区的加权二分匹配
我这里有一个问题，我设法将其简化为加权二分匹配问题。基本上，我有一个带有分区 A 和 B 的二分图，以及一组带有权重的边。就我而言，|A|~=20 和 |B| =300。
我想找到一组最小化权重的边并覆盖'A'（A上的每条边都有一个关联的解决方案边）
问题：
-这种问题是否有一个特殊的名称，所以我可以寻找算法和解决方案吗？
-我知道我可以通过在 A 上添加具有无限权重的虚拟顶点，将其简化为加权二分完美匹配。但自 |B|>>|A| 以来，我担心实际性能。
- 对 Java 库有什么建议吗？我发现了这个：http://algs4.cs.princeton.edu/code/。我认为“AssignmentProblem.java”几乎就是我所需要的 - （但我想它不能确保完美匹配？）
提前致谢，并对糟糕的英语感到抱歉。
I have a problem here, that I managed to reduce to a weighted bipartite match problem. Basically, I have a bipartite graph with partitions A and B, and a set of edges with weights. In my case, |A|~=20 and |B| =300.
I want to find a set of edges which minimizes the weigths AND COVERS 'A' (each edge on A has an associated solution edge)
Questions:
-Is there a special name for this kind a problem, so I can look for algorithms and solutions?
-I know I can reduce it to a weighted bipartite perfect match, by adding dummy vertices on A, with infinite weigth. But I'm worried about practical performance since |B|>>|A|.
-Any suggestions on Java libraries? I found this: http://algs4.cs.princeton.edu/code/. I think the 'AssignmentProblem.java' is almost what I need - (but I guess it doesn't ensure a perfect matching?)
Thanks in advance and sorry about the bad english.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
a) 最大加权完美匹配
b) ???
c) floyd 或 floyd-warshall 算法是你的朋友，
我在网上找到了一个 c 实现，你也可以使用 edmond 的开花算法。
a) maximum weighted perfect matching
b) ???
c) floyd or floyd-warshall alogorithm is your friend
I've found a c-implemenation in the web and also you can use edmond's blossom algorithm, too.