P2656 采蘑菇

    • 397通过
    • 1.8K提交
  • 题目提供者 NOIRP
  • 评测方式 云端评测
  • 标签 SPFA 图论 强连通分量,缩点 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小胖和ZYR要去ESQMS森林采蘑菇。

    ESQMS森林间有N个小树丛,M条小径,每条小径都是单向的,连接两个小树丛,上面都有一定数量的蘑菇。小胖和ZYR经过某条小径一次,可以采走这条路上所有的蘑菇。由于ESQMS森林是一片神奇的沃土,所以一条路上的蘑菇被采过后,又会长出一些新的蘑菇,数量为原来蘑菇的数量乘上这条路的“恢复系数”,再下取整。

    比如,一条路上有4个蘑菇,这条路的“恢复系数”为0.7,则第一~四次经过这条路径所能采到的蘑菇数量分别为4,2,1,0.

    现在,小胖和ZYR从S号小树丛出发,求他们最多能采到多少蘑菇。

    对于30%的数据,N<=7,M<=15

    另有30%的数据,满足所有“恢复系数”为0

    对于100%的数据,N<=80,000,M<=200,000,0.1<=恢复系数<=0.8且仅有一位小数,1<=S<=N.

    输入输出格式

    输入格式:

    第一行,N和M

    第2……M+1行,每行4个数字,分别表示一条小路的起点,终点,初始蘑菇数,恢复系数。

    第M+2行,一个数字S

    输出格式:

    一个数字,表示最多能采到多少蘑菇,在int32范围内。

    输入输出样例

    输入样例#1: 复制
    3 3
    1 2 4 0.5
    1 3 7 0.1
    2 3 4 0.6
    1
    输出样例#1: 复制
    8
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。