### _smhx's blog

By _smhx, history, 14 months ago,

First blog post!

I want to write about a cool problem that appeared on the UKIEPC 2019 contest. Here is the statement:

You are a realtor in charge of buying and selling homes for $n \leq 100$ families. In total, there are $m \leq n(n-1)$ offers, with the $i$'th offer being family $a_i$ would like to buy family $b_i$'s home for $c_i$ dollars ($a_i \neq b_i$). In addition, the pair $(a_i, b_i)$ will occur at most once in the input.

The families agree that they will all purchase simultaneously, or stay in their original home. You earn a fixed commission of 5% on each purchase. How can you select a subset of purchases such that nobody ends up homeless and you maximise your earnings?

This problem is equivalent to the following: Given a weighted directed graph, decompose the graph into vertex disjoint cycles with maximum edge sum. Specifically, the vertices are the $n$ families, and the edges are from $a_i$ to $b_i$ with weight $c_i$. Your earnings are then just 5% of this sum.

The solution comes from this observation: A cycle decomposition can be described as a matching $dest_i$, the destination of family $i$ after all purchases. The matching requirement is $dest_i \neq dest_j$ if $i \neq j$, i.e., no two families share a home. We would like to maximise the sum of the values of each matching, which we define now: If there is an edge from $i$ to $dest_i$, then the value of the matching is the weight of the edge. Otherwise, if $i = dest_i$ the value is 0. Finally, in all other cases the value is $-\inf$. We can easily convert this to a minimisation problem by taking negatives and then apply the Hungarian algorithm in $n^3$ time.

Can anyone share other interesting problems involving matchings?

• +16

 » 14 months ago, # | ← Rev. 2 →   +8 Similar problem. This one and this one from coci. The problem from the post appeared before in SWERC14 as problem D.