P2784 化学1(chem1)- 化学合成

    • 222通过
    • 830提交
  • 题目提供者 HansBug 管理员
  • 评测方式 云端评测
  • 标签 图论 邻接矩阵 邻接表 队列 洛谷原创 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    蒟蒻HansBug在化学考场上,挠了无数次的头,可脑子里还是一片空白。

    题目描述

    眼下出现在蒟蒻HansBug面前的是一个化学合成题,据他所知,一般答案如下面这样的格式:

    (接下一行)

    简单解释下:每种化合物可以通过一步反应生成另一个化合物(将这称作一步反应,设为 A--->B),现在假设每个A--->B中,理论上1个单位的A都仅可以生成1个单位的B。然而实际实验表明,并不存在绝对完全的化学转化,设转化率为C(即1个单位A实际可以生成C个单位的B,0<C<1)。

    现在蒟蒻HansBug的知识体系中有N个这样A--->B的转化。然而题目中蒟蒻HansBug要由1个单位的化合物S生成化合物T,可是他脑细胞和RP已经消耗殆尽,所以找到最终产量最高的合成路线的艰巨任务就交给你啦!

    输入输出格式

    输入格式:

    第一行为4个整数:N、M、S、T,分别表示总共出现的化合物个数、HansBug所知道的反应个数、起始的化合物序号、终末的化合物序号。(1<=S、T<=N)

    第2-M+1行每行为两个整数和一个实数:Ai、Bi、Ci,分别表示第i个反应为由1个单位的Ai化合物生成Ci单位的Bi化合物。

    输出格式:

    一行,包含一个实数,为最佳路线下最终的产量(四舍五入保留4位小数),如果没有可行路线的话,输出orz。

    输入输出样例

    输入样例#1: 复制
    3 3 1 3
    1 3 0.8
    1 2 0.9
    2 3 0.9
    
    输出样例#1: 复制
    0.8100
    输入样例#2: 复制
    3 3 2 1
    1 3 0.8
    1 2 0.9
    2 3 0.9
    
    输出样例#2: 复制
    orz

    说明

    样例1和样例2中,两条合成路线分别为1--->3、1--->2、2--->3,产率分别为0.8、0.9、0.9。

    在样例1中,有两种可行的路线1--->3和1--->2--->3,最终产量分别为0.8、0.9*0.9=0.81,故第二条路线更优,产量为0.8100。

    样例2中,2只能生成3,3无法生成别的化合物,故无法生成,蒟蒻HansBug只好选择orz。

    样例数据:

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