P4630 [APIO2018] Duathlon 铁人两项

    • 400通过
    • 857提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 割点 APIO 2018 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 1024MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    警告!滥用本题者封号!请勿多次重复提交!

    题目描述

    比特镇的路网由 $m$ 条双向道路连接的 $n$ 个交叉路口组成。

    最近,比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程:选手先完成一段长跑赛程,然后骑自行车完成第二段赛程。

    比赛的路线要按照如下方法规划:

    1. 先选择三个两两互不相同的路口 $s, c$和 $f$,分别作为比赛的起点、切换点(运动员在长跑到达这个点后,骑自行车前往终点)、终点。
    2. 选择一条从 $s$出发,经过 $c$最终到达 $f$的路径。考虑到安全因素,选择的路径经过同一个点至多一次。

    在规划路径之前,镇长想请你帮忙计算,总共有多少种不同的选取 $s, c$和 $f$的方案,使得在第 $2$步中至少能设计出一条满足要求的路径。

    输入输出格式

    输入格式:

    第一行包含两个整数 $n$和 $m$ ,分别表示交叉路口和双向道路的数量。

    接下来 $m$行,每行两个整数 $v_i, u_i$ 。表示存在一条双向道路连接交叉路口 $v_i, u_i$ $(1 ≤ v_i, u_i ≤ n,v_i \neq u_i)$。

    保证任意两个交叉路口之间,至多被一条双向道路直接连接。

    输出格式:

    输出一行,包括一个整数,表示能满足要求的不同的选取 $s, c$和 $f$的方案数。

    输入输出样例

    输入样例#1: 复制
    4 3
    1 2
    2 3
    3 4
    
    输出样例#1: 复制
    8
    
    输入样例#2: 复制
    4 4
    1 2
    2 3
    3 4
    4 2
    
    输出样例#2: 复制
    14
    

    说明

    提示

    在第一个样例中,有以下 $8$种不同的选择 $(s, c, f)$的方案: $(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4),$ $(3, 2, 1), (4, 2, 1), (4, 3, 1), (4, 3, 2)$。

    在第二个样例中,有以下 $14$种不同的选择 $(s, c, f)$ 的方案: $(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 3), (2, 3, 4), (2, 4, 3),$ $(3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2),$ $(4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)$。

    子任务(注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)

    • Subtask 1(points: $5$): $n \leq 10, m \leq 100$
    • Subtask 2(points: $11$): $n \leq 50, m \leq 100$
    • Subtask 3(points: $8$): $n \leq 100000$,每个交叉路口至多作为两条双向道路的端点
    • Subtask 4(points: $10$): $n \leq 1000$,在路网中不存在环(存在环是指存在一个长度为 $k (k ≥ 3)$ 的交叉路口序列 $v_1, v_2,..., v_k$,序列中的路口编号两两不同,且对于 $i$从 $1$到 $k - 1$,有一条双向道路直接连接路口 $v_i$和 $v_{i+1}$,且有一条双向道路直接连接路口 $v_k$和$v_1$)
    • Subtask 5(points: $13$): $n \leq 100000$,在路网中不存在环
    • Subtask 6(points: $15$): $n \leq 1000$,对于每个交叉路口,至多被一个环包含
    • Subtask 7(points: $20$): $n \leq 100000$,对于每个交叉路口,至多被一个环包含
    • Subtask 8(points: $8$): $n \leq 1000, m \leq 2000$
    • Subtask 9(points: $10$): $n \leq 100000, m \leq 200000$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。