Editorial for COCI '09 Contest 7 #4 Svemir
Submitting an official solution before solving the problem yourself is a bannable offence.
First, you need to know at least one way of constructing minimum spanning trees, e.g. Kruskal's algorithm.
We claim that tunnels need to be constructed only between planets that are immediate neighbors on one of the axis. This can be easily proven. Suppose there are two planets ( and
) and that tunnel cost between
and
is
. Now suppose that
and
are not immediate neighbors on the
axis. In other words, there is some planet
such that
. It is easy to see that instead of constructing one tunnel from
to
we can construct two tunnels:
and
that cost less than or equal to tunnel
since
.
We are nearly done now. We simply construct a graph of all planets with links between immediate neighbors. Using Kruskal's algorithm, we obtain a minimal cost fully connected network.
Comments