最大重量双边匹配 [英] Maximum weight bipartite matching

问题描述

我有一个图中矩形网格的形式，即N个节点和2N边，所有相邻节点连接。 这意味着它是双似是，因此它是可以做到的二分匹配就可以了。

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.

每个（无向）边有一个分配给它的重量 - 无论是-2，-1，0，1或2。没有其他的值被允许

Each (undirected) edge has a weight assigned to it - either -2, -1, 0, 1 or 2. No other values are allowed

我将如何去寻找这个图，最大化的匹配晕死的总和匹配？伪code将是很好的，不与特定的语言打扰。

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.

在理想情况下，我找了一个运行在二次时间的算法 - 也许为O（n ^ 2 log n）的最坏

Ideally, I am looking for an algorithm that runs in quadratic time - maybe O(n^2 log n) at worst.

在你提出一个解决方案，我已经试过那么重1做用重2边的最大的比赛，（而不超过重量的2边）。我曾与这个实现得分98％（这个问题是从信息学奥林匹克竞赛），并想知道什么是100％的解决方案。

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.

推荐答案

不知道为什么你所想的分切。一个切口不能保证让你在这种情况下匹配。你需要做的是解决分配问题。分配问题 。历届最短的数学算法，解决它的O（EV日志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).

这篇关于最大重量双边匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！