#P1431. MLand
MLand
题目描述
给出一个连通的带权无向图,边的权值是关于时间的线性函数。
第 条边 时刻的权值为 。
求出在时间段 内,最小生成树权和能够达到的最大值。时间可以取实数。
输入格式
第一行四个整数 , 和 分别为点数和边数,点从 到 编号。
下面 行每行四个整数 ,分别描述每条边连接的端点编号和边权关于时间的变化关系。
输出格式
输出一个浮点数,表示区间内最小生成树权和的最大值,保留三位小数。
按最接近的千分之一舍入;恰为半个单位时按绝对值进一,例如 输出 0.001, 输出 -0.001。舍入为零时输出 0.000。
本站原评测数据及参考程序只输出这个最大权和。旧存档将输出误写成“时刻和权和”,本次统一更正为与全部原评测数据一致的单个数,不改变任何输入或答案。
5 6 0 5
1 0 -6 -4
2 0 3 -3
3 0 1 5
3 1 -2 -3
4 1 -3 -2
4 3 -2 -3
-13.000
数据规模与约定
对于 的数据,,。
补充数值范围:,。本地版本的 范围以上文 为准,采用单组输入。