Maximum weight bipartite matching

Question

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.

Answer 1

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).