1 条题解

  • 0
    @ 2026-11-15 13:16:50

    题目分析

    我们先给一个图。

    T3-1

    由图可知有 $(1,8),(1,9),(1,10),(2,8),(2,9),(2,10),(3,8),(3,9),(3,10)$ 这几对点满足题意要求。

    通过观察可以发现 aa 与 bb 之间的节点所通向的路径,无论是通向 aa 的左边,还是通向 bb 的右边,都不会包含 aa 或 bb。

    假设以节点序号较小为起点,较大为终点,我们可以得到:以 aa 左边的节点为起点,以 bb 右边的节点为终点,所构成的路径一定包含 aa 与 bb。

    T3-1

    显然,一个节点把图分为两边,那么图的左边除了经过该节点,没有可以不经过该节点而到达图的右边的路径。也就是,这个节点无可避免地经过 aa 和 bb,无法绕路。而最后 (u,v)(u,v) 的数量,就是 aa 左边的节点数量 ×\times bb 右边的节点数量。

    考虑搜索。我们先假定起点为 aa,终点为 bb。从 aa 出发开始搜,到 bb 为止,没有搜到的点就是 bb 右边的点。(参见下图)

    T3-1

    黄线为以 aa 为起点会搜到的路径,只要给搜到的点打上标记,就可以知道 bb 右边点的数量。同理,我们以 bb 为起点,也可以搜出 aa 左边的点。两边的答案相乘,就可以得到题目的答案。

    那么如何实现呢?

    • 设一个记录访问的数组 flfl。

    • 给终点(aa 或 bb)先打上标记,搜到那里时就停。

    • 只要碰到没有搜过的,就继续搜下去。因为终点已经打上标记的,而且是联通图,所以没搜到的点就一定是 aa 左边或 bb 右边。

    这样,我们很容易使用 bfs 或 dfs 解决此题。

    • 1

    信息

    ID
    54
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者