Problem 6: Amanda Lounges

https://open.kattis.com/problems/amanda

What makes this graph problem really interesting is that it gives us three different types of edges: 0 lounges, 1 lounge, and 2 lounges. At first glance, this seems to complicate things quite a bit, but it becomes a bit simpler when we break down the cases:

• 0 Lounges: We know for certain that neither airport can have a lounge.

• 1 Lounge: Either of the nodes can have a lounge.

• 2 Lounges: We know for certain that both airports must have a lounge.

We can see that of the three cases, two of them - the case of 0 and 2 lounges - give us information. We know that for two airports either there will absolutely be lounges there (2 lounges), or there absolutely won’t (0 lounges). So, all we really need to figure out how to deal with the 1 lounge case.

In the case of 1 lounge, by definition every connected pair of airports only 1 can have a lounge. The key insight is, If we considered just these edges alone, this problem would be a simple case of determining whether or not this graph is bipartite! So... why don’t we just do that? We create a graph that consists only of the edges where c == 1. To account for the cases with 0’s and 2’s, we can colour those edges as “no lounges” or “lounges” respectively, without including them in our graph. From here, all we need to do is propagate the colours throughout the graph to see if there’s a possible bipartite matching. In the case where no colours are fixed in a connected component, add the colour used the least times to your lounge total.

The graph is not necessarily connected! Be sure to check every connected component for biparititeness.