P1931 套利

    • 31通过
    • 91提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 SPFA 图论
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    套利是利用汇率差异实现货币增值。例如,1美元可以兑换0.5英镑、1英镑可以兑换10法郎、1法郎可以兑换0.21美元。接下来,一个聪明的交易商就可以从1美元开始,0.5 * 10.0 * 0.21 =1.05美元,获得了5%的利润。

    你的任务是写一个程序,从输入文件读入汇率清单,然后决定套利是有可能的或没有可能的。

    输入输出格式

    输入格式:

    输入文件包含多组数据,每组数据的第一行是一个整数n( 1<=n<=30 )。代表有多少种货币。接下来n行字符串,每行表示一种货币的名称(名称中不会出现空格)。下一行是一个整数m,约定了汇率表的长度。随后的m行中,每行有三部分组成。The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. 每组数据之间空一行。当n=0时表示输入数据结束。

    输出格式:

    第i组数据,输出Case i: 后,如果可以套利,输出Yes,否则输出No。

    输入输出样例

    输入样例#1: 复制
    3
    USDollar
    BritishPound
    FrenchFranc
    3
    USDollar 0.5 BritishPound
    BritishPound 10.0 FrenchFranc
    FrenchFranc 0.21 USDollar
    
    3
    USDollar
    BritishPound
    FrenchFranc
    6
    USDollar 0.5 BritishPound
    USDollar 4.9 FrenchFranc
    BritishPound 10.0 FrenchFranc
    BritishPound 1.99 USDollar
    FrenchFranc 0.09 BritishPound
    FrenchFranc 0.19 USDollar
    
    0
    
    输出样例#1: 复制
    Case 1: Yes
    Case 2: No
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。