最大权重二分匹配
我有一个矩形网格形式的图，即N个节点和2N条边，所有相邻节点都是连接的。 这意味着它是双色的，因此可以对其进行二分匹配。
每个（无向）边都分配有一个权重 - -2、-1、0、1 或 2。不允许使用其他值
我将如何在该图上找到匹配项，以最大化权重总和匹配？伪代码会很好，不用担心特定的语言。
理想情况下，我正在寻找一种以二次方时间运行的算法 - 最坏的情况可能是 O(n^2 log n) 。
在您提出解决方案之前，我已尝试使用权重 2 的边进行最大匹配，然后使用权重 1 的边（不超过权重 2 的边）。我通过这个实现获得了 98% 的分数（问题来自信息学奥林匹克竞赛），并且想知道 100% 的解决方案是什么。
I have a graph in form of a rectangular grid, i.e. N nodes and 2N edges, all adjacent nodes are connected.
This means it is two-colourable, and hence it is possible to do bipartite matching on it.
Each (undirected) edge has a weight assigned to it - either -2, -1, 0, 1 or 2. No other values are allowed
How would I go about finding the matching on this graph that maximises the sum of the weighs in the matching? Pseudocode would be nice, don't bother with specific languages.
Ideally, I am looking for an algorithm that runs in quadratic time - maybe O(n^2 log n) at worst.
Before you propose a solution, I have tried doing a max match using edges of weight 2, then of weight 1 (without going over edges of weight 2). I have scored 98% with this implementation (the problem is from an informatics olympiad), and wondering what is the 100% solution.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不知道你为什么要考虑最小切割。在这种情况下，不能保证剪切能够为您提供匹配。你需要做的是解决作业问题。作业问题 。连续最短数学算法在 O(EV log V) 中解决它，在您的情况下是 O(n^2 log n)。
Not sure why you are thinking of min cut. A cut is not guaranteed to give you matching in this case. What you need to do is solve assignment problem.Assignment Problem. The successive shortest math algorithm solves it in O(EV log V) which in your case is O(n^2 log n).