[USACO19DEC] 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$ 乘以最优解的值,并向下取整(也就是说,如果这个数本身不是整数,输出小于它的最接近它的整数)。
输入输出样例
输入样例 #1
3 2
2 1 2 4
2 3 5 3
输出样例 #1
428571
说明
在这个例子中,仅由一条路径从 $1$ 到 $N$。 它的流量为 $\min(3,4)=3$,花费为 $2+5=7$。
### 数据范围
测试点 $2\sim 5$ 满足 $N,M\le 100$。
对于 $100\%$ 的数据,$2 \leq N \leq 1000$,$1 \leq M \leq 1000$。
供题:Brian Dean