#P2395. [Balkan 2011]Timeismoney

    ID: 1438 传统题 2000ms 128MiB 尝试: 930 已通过: 307 难度: 8 上传者: 标签>CF2400省选/NOI-凸包Kruskal分治算法叉积普通并查集自定义排序规则

[Balkan 2011]Timeismoney

题目描述

有 nn 个城市(编号从 0…n−10\dots n-1),mm 条公路(双向的),从中选择 n−1n-1 条边,使得任意的两个城市能够连通,一条边需要的 cc 的费用和 tt 的时间,定义一个方案的权值 vv 为 n−1n-1 条边的费用和 ×\times n−1n-1条边的时间和,你的任务是求一个方案使得 vv 最小。

输入格式

第一行两个整数 n,mn,m,接下来每行四个整数 a,b,c,ta,b,c,t,表示有一条公路连接城市 aa 与城市 bb 需要 tt 时间和 cc 费用。

输出格式

仅一行两个整数 sumc,sumtsumc,sumt,(sumcsumc 表示使得 vv 最小时的费用和,sumcsumc表示最小的时间和) 如果存在多个解使得 sumc×sumtsumc\times sumt 相等,输出 sumcsumc 最小的。

样例输入

5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92

样例输出

279 501

数据规模与约定

有 5%5\% 的数据 m=n−1m=n-1。

有 40%40\% 的数据有 t=ct=c。

对于 100%100\% 的数据 1≤n≤2001\le n\le 200,1≤m≤1041\le m\le 10^4,0≤a,b≤n−10\le a,b\le n-1,0≤t,c≤2550\le t,c\le 255。