P1710 地铁涨价

    • 131通过
    • 648提交
  • 题目提供者洛谷OnlineJudge
  • 标签 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    本题开O2优化,请注意常数

    题目描述

    博艾市除了有海底高铁连接中国大陆、台湾与日本,市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站,同时有M小段地铁连接两个不同的站。

    地铁计价方式很简单。从A站到B站,每经过一小段铁路(连接直接相邻的两个点的一条边),就要收取1博艾元。也就是说,从A站到B站,选择的路径不一样,要价也会不同。

    我们认为凡华中学在1号地铁站。学生们通过地铁通勤,他们当然知道选择最短路来坐车的话,票价最便宜。

    然而博艾地铁公司经营不善,一直亏损,于是他们打算提价。提价一次就是将一小段铁路原来收费1元改收2元。同一小段的铁路不会多次提价。他们打算提价Q次。

    学生们知道,如果他们到学校的一条最短路径中的一小段提价了,可以改变路径,使总票价不变。然而随着一条一条的铁路被提价,当居住在某个站附近的学生发现,提价后,没有任何一种方案可以从家到学校的费用和初始费用相等时,就会不满。

    现在地铁公司希望知道,对于每一次涨价,有多少个站,学生会因为涨价而不满呢?

    输入输出格式

    输入格式:

    第一行为三个整数N,M,Q。

    接下来M行,每行2个整数ai,bi,表示第i条铁路连接的两个站。i表示铁路编号。

    接下来Q行,每行一行整数rj,表示每次涨价的铁路编号。

    输出格式:

    Q行。每行一个整数表示不满的车站数量。

    输入输出样例

    输入样例#1: 复制
    5 6 5
    1 2
    1 3
    4 2
    3 2
    2 5
    5 3
    5
    2
    4
    1
    3
    
    输出样例#1: 复制
    0
    2
    2
    4
    4

    说明

    【样例解释】

    次数 车站2 车站3 车站4 车站5
    初始 1     1     2     2
    1    1     1     2     2
    2    1     2     2     3
    3    1     2     2     3
    4    2     2     3     3
    5    2     2     4     3

    【数据范围】

    对于20%的数据 N≤100, Q≤30

    对于40%的数据 Q≤30

    对于70%的数据 正确的输出结果中,不会有超过50种不一样的整数(数据范围剧透解法系列)

    对于100%的数据 N≤100000, Q≤M≤200000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。