3319. [USACO19 DEC Gold]Milk Pumping

【题目描述】

Farmer John 最近为了扩张他的牛奶产业帝国而收购了一个新的农场。这一新的农场通过一个管道网络与附近的小镇相连，FJ 想要找出其中最合适的一组管道，将其购买并用来将牛奶从农场输送到小镇。

这个管道网络可以用N 个接合点（管道的端点）来描述，将其编号为1…N（2≤N≤1000）。接合点 1 表示 FJ 的农场，接合点N 表示小镇。有M 条双向的管道（1≤M≤1000），每条连接了两个接合点。使用第i 条管道需要 FJ 花费ci 美元购入，可以支持每秒fi 升牛奶的流量。

FJ 想要购买一条管道组成一条单一路径，路径的两端点分别为接合点 1 和N。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量（因为这是沿这条路径输送牛奶的瓶颈）。FJ 想要最大化路径流量与路径花费之比。保证存在从1 到N之间的路径。

【输入格式】

输入的第一行包含N 和M。以下M 行每行以四个整数描述一条管道：a 和b（管道连接的两个不同的接合点），c（管道的花费），以及 f（管道的流量）。花费和流量均为范围1…1000 之内的正整数。

【输出格式】

输出10^6乘以最优解的值，并向下取整（也就是说，如果这个数本身不是整数，输出小于它的最接近它的整数）。

【样例输入】

3 2

2 1 2 4

2 3 5 3

【样例输出】

428571

【提示】

测试点性质：

测试点 2-5 满足N,M≤100。

【来源】

在此键入。