P4951 [USACO 2001 OPEN]地震

    • 149通过
    • 317提交
  • 题目提供者 fhzwt
  • 评测方式 云端评测
  • 标签 生成树 USACO 2001(或之前)
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一场地震把约翰家的牧场摧毁了, 坚强的约翰决心重建家园。 约翰已经重建了N个牧场,现在他希望能修建一些道路把它们连接起来。研究地形之后,约翰发现可供修建的道路有M条。碰巧的是,奶牛们最近也成立一个工程队,专门从事修复道路。而然,奶牛们很有经济头脑,如果无利可图,它们是不会干的。

     奶牛们关注的是挣钱速度,即总利润和总施工时间的比值。约翰和奶牛达成了协议,奶牛负责修建道路,将所有牧场连通,而约翰需要支付F元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的,不过也有可能一些道路的建造成本之和会超过F。  
    
    请帮助奶牛们选择修复哪些道路,才能使单位时间的利润最大?  

    输入输出格式

    输入格式:

    第一行:三个整数: N,M和F,$1 ≤ N ≤ 400$, $1 ≤ M ≤ 10000$,$1 ≤ F ≤ 2 × 10^9$
    第二行到$M + 1$行:第$i + 1$行表示第i条道路的信息,有四个整数:$U_i$ ,$V_i$ ,$C_i$ 和$T_i$ ,$U_i$ 和$V_i$ 表示这条道路连接的牧场编号,Ci表示道路修建的成本,Ti表示道路修建所需要的时间,$1 ≤ U_i ≤ N$,$1 ≤ V_i ≤ N$,$1 ≤ C_i ≤ 2 × 10^9 $,$1 ≤ T_i ≤ 2 × 10^9$

    输出格式:

    第一行:一个保留四位小数的浮点数,表示奶牛们能挣到的最大单位时间利润,如果奶牛们无钱可赚,则输出 0.0000

    输入输出样例

    输入样例#1: 复制
    5 5 100
    1 2 20 5
    1 3 20 5
    1 4 20 5
    1 5 20 5
    2 3 23 1
    输出样例#1: 复制
    1.0625

    说明

    (奶牛们可以选择连通最后四条道路,则总 时间为 16,总成本为 83,所以单位利润为 17/16 = 1.0625)

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