COCI-自行车赛题解

英文题解的翻译:

自行车赛

First we observe that any path ending in city 1 has a corresponding path starting in city 1.

  首先我们可以发现,所有以1号结点为终点的路径,都有一个以1号结点为起点的路径与其对应。

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 1.

  使事情变得更简单,我们会尝试着去找以1号结点为起点的最长路。

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.

  为了A掉这道题,我们必须首先判断出环和割边。

One of the ways of doing this is by constructing a DFS tree from node 1

  解决这个问题,我们可以用$Tarjan$算法建出一个以1号结点为根结点的$dfs$树,

and calculating all standard values(discovery time, finish time, lowlink value).

  并且将该算的值(`dfn[]`和`low[]`)都算完。

Details can be found in the source code.

  代码的具体实现以及细节可以在std里面找到(???)。

For a given ring we say that it "hangs" from node X if node X is the highest node in the DFS tree in that ring.

  对于一个给定的环,我们称其“悬挂”在一个点上,当且仅当这个点的$dfn$值是这个环上最大的。

For a given bridge we say that it "hangs" from node X if node X is the higher node in the DFS tree.

  对于一个给定的割边,我们称其“悬挂”在一个点上,当且仅当这个点的$dfn$值是两者中较大的那个。

For each node X we define a subgraph of node X

  对于每个结点$x$,我们定义$x$的子图

as the union of node X and all subgraphs of all nodes lying in rings "hanging" from X

and all subgraphs of all nodes on other sideof bridges "hanging" from X.

  为$x$、“悬挂”在$x$上的所有环上的点的子图

  以及“悬挂”在$x$上的所有割边上的点的子图的并。

For each node X we need to find two numbers,

  对于每个结点我们要求出两个值:

circle(X) - path inside subgraph of node X starting and ending in X,

  $circle(x)$ - $x$的子图中,始于$x$并且终于$x$的路径长度,

and path(x) - path inside subgraph of X starting in X and ending in anynode.

  $path(x)$ - $x$的子图中,始于$x$,而终于任意一个点的路径长度。

circle(X) can be calculated by simple recursion

  $circle(x)$用简单的递归就可以求出:

as sum of lengths of all rings "hanging" from X

  它作为所有“悬挂”在$x$上的环的长度之和,

and sum of all circle(Y) for each node Y lying on those rings

  以及所有“悬挂”在那些环上的结点$y$的$circle(y)$之和

(because we can take the circle on any node Y and end up back at Y).

  (因为我们可以从$y$开始,遍历这个环,再从$y$结束)。

When calculating path(X) we need to take into account the following possible scenarios, selecting the one that yields the longest path:

  当我们在计算$path(x)$的时候,我们需要考虑下面所提到的几种可能的情况,选择那个能提供最长路的一个:
  1. The path from X ends in X. This leads to path(X)= circle(X).
  1. 始于$x$,并终于$x$的路径,这样的话$path(x) = circle(x)$。
  1. We can first make a circle in subgraph of X, and then take one bridge "hanging" from X into a new subgraph giving: path(X) = circle(X) + path(Y) where Y is the node on the otherside of the bridge.
  2. 我们可以先跑完$x$的子图中的所有环,然后再跑一个割边,使得$path(x) = circle(x) + path(y)$,其中$y$是割边的两个点中异于$x$的那个点。

  **注:*make a circle*的意思并不是只走一个环,而是绕圈圈的意思,意译过来就是遍历完所有的环。**
  1. We can make a circle in all rings "hanging" from X except one and than select one city in that ring as the ending.

    In that case there are two possible ways to arrive to the selected city so we need to find the longer.

  3. 我们可以少跑一个环,并跑完$x$的子图中其他的所有环,并以那个少跑的环上的某个结点作为终点。

  那样的话就有两种方案,我们要选择两者中的较长的。

The solution is then path(1). Details on how to implement this can be found in the source code.

  那么答案就是$path(1)$。实现这道题的细节问题,可以看$std$是怎么处理的(???)。
原文地址:https://www.cnblogs.com/zzqdeco/p/12897569.html