TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4766
  • 题目
  • P4766【APIO2018】铁人两项
    限制 : 时间限制 : 40000 MS   空间限制 : - KB
    评测说明 : 1s 1G
    问题描述

    比特镇的路网由 \(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 \le v_i, u_i \le 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

    提示

    样例输入1

    4 3
    1 2
    2 3
    3 4
    

    样例输出1

    8
    

    样例解释1

    在第一个样例中,有以下 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)\)

    样例输入2

    4 4
    1 2
    2 3
    3 4
    4 2
    

    样例输出2

    14
    

    样例解释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)\)

    子任务 1(5 分):\(n \le 10\), \(m \le 100\)

    子任务 2(11 分):\(n \le 50\), \(m \le 100\)

    子任务 3(8 分):\(n \le 100\,000\), 每个交叉路口至多作为两条双向道路的端点。

    子任务 4(10 分):\(n \le 1\,000\), 在路网中不存在环。

    存在环是指存在一个长度为 \(k\) (\(k\ge 3\)) 的交叉路口序列 \(v_1, v_2, \ldots v_k\) ,序列中的路口编号两两不同,且对于 \(i\) 从 $1$ 到 \(k-1\) ,有一条双向道路直接连接路口 \(v_i\)\(v_{i+1}\) ,且有一条双向道路直接连接路口 \(v_k\)\(v_1\)

    子任务 5(13 分):\(n \le 100\,000\), 在路网中不存在环。

    子任务 6(15 分):\(n \le 1\,000\), 对于每个交叉路口,至多被一个环包含。

    子任务 7(20 分):\(n \le 100\,000\), 对于每个交叉路口,至多被一个环包含。

    子任务 8(8 分):\(n \le 1\,000\), \(m \le 2\,000\)

    子任务 9(10 分):\(n \le 100\,000\), \(m \le 200\,000\)