F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 1431. -- MLand

1431: MLand

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 14  Solved: 4
[Submit][Status][Discuss]

Description

给出一个带权无向图,边的权值是关于权值成线性关系的.
第i条边t时刻的权值为Ai*t+Bi.
求出在时间段[t1,t2]内使最小生成树权和最大的时刻和此时的权和

Input

第一行四个正整数n,m,t1,t2 n和m分为点数和边数,点从0到n-1编号 
下面m行每行四个整数uv,a,b,分别描述每条边连接的端点编号和边权关于时间的变化关系.
N<=200,M<=1200

Output

只需要输出最小生成树权和的最大值

Sample Input

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

Sample Output

-13.000

HINT

Source

[Submit][Status][Discuss]

HOME Back