#P1431. MLand

    ID: 442 传统题 1000ms 512MiB 尝试: 39 已通过: 12 难度: 8 上传者: 标签>CF2400提高+/省选-Kruskal普通并查集自定义排序规则凸性/单峰性判定实数二分有理数精确运算定点数十进制舍入

MLand

题目描述

给出一个连通的带权无向图,边的权值是关于时间的线性函数。

第 ii 条边 tt 时刻的权值为 ai×t+bia_i\times t+b_i。

求出在时间段 [t1,t2][t_1,t_2] 内,最小生成树权和能够达到的最大值。时间可以取实数。

输入格式

第一行四个整数 n,m,t1,t2n,m,t_1,t_2,nn 和 mm 分别为点数和边数,点从 00 到 n−1n-1 编号。

下面 mm 行每行四个整数 u,v,a,bu,v,a,b,分别描述每条边连接的端点编号和边权关于时间的变化关系。

输出格式

输出一个浮点数,表示区间内最小生成树权和的最大值,保留三位小数。

按最接近的千分之一舍入;恰为半个单位时按绝对值进一,例如 0.00050.0005 输出 0.001,−0.0005-0.0005 输出 -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

数据规模与约定

对于 100%100\% 的数据,1≤n≤2001\leq n\leq 200,1≤m≤1.2×1031\leq m\leq 1.2\times 10^3。

补充数值范围:−10000≤t1≤t2≤10000-10000\le t_1\le t_2\le10000,−32000≤ai,bi≤32000-32000\le a_i,b_i\le32000。本地版本的 n,mn,m 范围以上文 n≤200,m≤1200n\le200,m\le1200 为准,采用单组输入。