Milk Pumping G

题目描述:

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

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

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

输入格式:

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

输出格式:

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

数据范围:

测试点 \(2\sim 5\) 满足 \(N,M\le 100\)。

对于 \(100\%\) 的数据，\(2 \leq N \leq 1000\)，\(1 \leq M \leq 1000\)。

样例输入:

3 2
2 1 2 4
2 3 5 3

样例输出:

428571

提示:

在这个例子中，仅由一条路径从 \(1\) 到 \(N\)。 它的流量为 \(\min(3,4)=3\)，花费为 \(2+5=7\)。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO2019 Dec gold