Editorial for COCI '07 Contest 1 #6 Staza
Submitting an official solution before solving the problem yourself is a bannable offence.
First we observe that any path ending in city has a corresponding path starting in city
. It is sufficient to reverse the sequence of roads forming the path. To simplify things, we will be trying to find the longest path starting in city
.
If we observe the given network we can see that, speaking in graph theory terms, each road is either a part of a single ring, or a bridge.
In order to solve the problem, we must first identify rings and bridges. One of the ways of doing this is by constructing a DFS tree from node and calculating all standard values (discovery time, finish time, lowlink value).
For a given ring we say that it "hangs" from node if node
is the highest node in the DFS tree in that ring. For a given bridge we say that it "hangs" from node
if node
is the higher node in the DFS tree.
For each node we define a subgraph of node
as the union of node
and all subgraphs of all nodes lying in rings "hanging" from
and all subgraphs of all nodes on the other side of bridges "hanging" from
.
For each node we need to find two numbers,
- path inside subgraph of node
starting and ending in
, and
- path inside subgraph of
starting in
and ending in any node.
can be calculated by simple recursion as sum of lengths of all rings "hanging" from
and sum of all
for each node
lying on those rings (because we can take the circle on any node
and end up back at
).
When calculating we need to take into account the following possible scenarios, selecting the one that yields the longest path:
- The path from
ends in
. This leads to
.
- We can first make a circle in subgraph of
, and then take one bridge "hanging" from
into a new subgraph giving:
where
is the node on the other side of the bridge.
- We can make a circle in all rings "hanging" from
except one and then select one city in that ring as the ending. In that case, there are two possible ways to arrive in the selected city so we need to find the longer way.
The solution is then .
Comments