## IPSC 2002

## Solution to Problem F – (un)Fair Play

Clearly if there is a solution, there is a solution where team **N** wins all its remaining
matches. Let **N** have **P** points after winning all its remaining matches. If some
other team has at least **P** points, there is no solution. Otherwise, we have to distribute
the points from the remaining matches between the other teams in such a way that no team
reaches or exceeds **P** points. We transform this task to an integer network flow problem.

Consider a graph with **2+M+(N-1)** vertices – a source, a sink, one vertex for each
remaining match and one for each team except the team **N**. From the source, an edge
with capacity 2 leads into each match-vertex (*). From
each match-vertex two edges with unlimited capacity lead into team-vertices of the
two teams playing the match (**). From each
team-vertex an edge leads to the sink (***). The capacity of this edge will be the maximum number
of points the team may still gain.

Edges (*) give each match two points to distribute. Edges (**) allow these points to be distributed
between the corresponding teams. Edges (***) enforce that after distributing the points, each team
will have less points than team **N**.

To solve the task, it suffices to find the maximum flow in the constructed graph (e.g. using the
Ford-Fulkerson algorithm) and verify, whether its value is **2M** – in other words, whether
it is possible to distribute all the remaining points.