Milk Pumping

题目描述

Farmer John 最近买了一座新农场来扩展他的牛奶生产帝国。新农场通过一张管道网络与附近的小镇相连，FJ 想找出最适合购买的一组管道，用于将牛奶从农场输送到小镇。

管道网络由 $N$ 个连接点（管道的端点）组成，方便起见编号为 $1 \ldots N$（$2 \leq N \leq 1000$）。连接点 1 表示 FJ 的农场，连接点 $N$ 表示小镇。有 $M$ 条双向管道（$1 \leq M \leq 1000$），每条连接一对连接点。第 $i$ 条管道的购买成本为 $c_i$ 美元，并且能支持每秒 $f_i$ 升牛奶的流量。

FJ 想购买一条从连接点 1 到连接点 $N$ 的单一路径上的管道。路径的成本是路径上所有管道成本之和。路径的流量是路径上所有管道流量的最小值（因为它会成为沿路径流动的瓶颈）。FJ 想最大化“路径流量 / 路径成本”。保证一定存在从 $1$ 到 $N$ 的路径。

评分： 测试点 2-5 满足 $N,M\le 100.$

输入格式

第一行输入包含 $N$ 和 $M$。 接下来的 $M$ 行每行用四个整数描述一条管道：$a$ 和 $b$（该管道连接的两个不同连接点）、$c$（其成本）、$f$（其流量）。成本和流量均为正整数，范围为 $1 \ldots 1000$。

输出格式

请输出最优解值的 $10^6$ 倍，并将结果截断为整数（即如果该数不是整数，则向下取整到不超过它的最大整数）。

3 2
2 1 2 4
2 3 5 3

428571

提示

在这个例子中，从 $1$ 到 $N$ 只有一条路径。其流量为 $\min(3,4)=3$，成本为 $2+5=7.$ 题目作者：Brian Dean

标签: USACO|2019|Gold

来源

USACO|2019|Gold