P3288 [SCOI2014]方伯伯运椰子

    • 194通过
    • 422提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 分数规划 网络流 负权环 2014 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    四川的方伯伯为了致富,决定引进海南的椰子树。方伯伯的椰子园十分现代化,椰子园中有一套独特的交通系统。

    现在用点来表示交通节点,边来表示道路。这样,方伯伯的椰子园就可以看作一个有 n + 2 个交通节点,m条边的有向无环图。n +1 号点为入口,n +2 号点为出口。每条道路都有 6 个参数,ui,vi,ai,bi,ci,di,分别表示,该道路从 ui 号点通向 vi 号点,将它的容量压缩一次要 ai 的花费,容量扩大一次要 bi 的花费,该条道路当前的运输容量上限为 ci,并且每单位运输量通过该道路要 di 的费用。

    在这个交通网络中,只有一条道路与起点相连。因为弄坏了这条道路就会导致整个交通网络瘫痪,聪明的方伯伯决定绝不对这条道路进行调整,也就是说,现在除了这条道路之外,对其余道路都可以进行调整。

    有两种调整方式:

    1. 选择一条道路,将其进行一次压缩,这条道路的容量会下降 1 单位。

    2. 选择一条道路,将其进行一次扩容,这条道路的容量会上升 1 单位。

    一条道路可以被多次调整。

    由于很久以前,方伯伯就请过一个工程师,对这个交通网络进行过一次大的优化调整。所以现在所有的道路都被完全的利用起来了,即每条道路的负荷都是满的(每条道路的流量等于其容量)。

    但方伯伯一想到自己的海南椰子会大丰收,就十分担心巨大的运输量下,会导致过多的花费。因此,方伯伯决定至少进行一次调整,调整之后,必须要保持每条道路满负荷,且总交通量不会减少。

    设调整后的总费用是 Y,调整之前的总费用是 X。现在方伯伯想知道,最优调整比率是多少,即假设他进行了 k 次调整,(X - Y)/k最大能是多少?

    注:总费用 = 交通网络的运输花费 + 调整的花费

    输入输出格式

    输入格式:

    第一行包含二个整数N,M接下来M行代表M条边,表示这个交通网络每行六个整数,表示Ui,Vi,Ai,Bi,Ci,Di接下来一行包含一条边,表示连接起点的边

    输出格式:

    一个浮点数,保留二位小数。表示答案,数据保证答案大于0

    输入输出样例

    输入样例#1: 复制
    5 10
    1 5 13 13 0 412
    2 5 30 18 396 148
    1 5 33 31 0 39
    4 5 22 4 0 786
    4 5 13 32 0 561
    4 5 3 48 0 460
    2 5 32 47 604 258
    5 7 44 37 75 164
    5 7 34 50 925 441
    6 2 26 38 1000 22
    输出样例#1: 复制
    103.00

    说明

     1<=N<=5000
    0<=M<=3000
    1<=Ui,Vi<=N+2
    0<=Ai,Bi<=500
    0<=Ci<=10000
    0<=Di<=1000
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。