logo AlgoBeat OnlineJudge
登录 注册

#101431. [BZOJ 1431] MLand

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出一个带权无向图,边的权值是关于权值成线性关系的。

条边 时刻的权值为

求出在时间段 内使最小生成树权和最大的时刻和此时的权和。

输入格式

第一行四个正整数 分别为点数和边数,点从 编号。

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

输出格式

一行两个浮点数,分别表示使最小生成树权和最大的时刻的此时的权和,保留三位小数。

样例

样例输入 #1

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

样例输出 #1

0.000 -13.000

数据范围与提示

对于 的数据,