USACO 2012 December Contest, Silver
Problem 3. Milk Routing
Contest has ended.
Log in to allow submissions in analysis mode
Problem 3: Milk Routing [Brian Dean, 2012]
Farmer John's farm has an outdated network of M pipes (1 <= M <= 500) for
pumping milk from the barn to his milk storage tank. He wants to remove
and update most of these over the next year, but he wants to leave exactly
one path worth of pipes intact, so that he can still pump milk from the
barn to the storage tank.
The pipe network is described by N junction points (1 <= N <= 500), each of
which can serve as the endpoint of a set of pipes. Junction point 1 is the
barn, and junction point N is the storage tank. Each of the M
bi-directional pipes runs between a pair of junction points, and has an
associated latency (the amount of time it takes milk to reach one end of
the pipe from the other) and capacity (the amount of milk per unit time
that can be pumped through the pipe in steady state). Multiple pipes
can connect between the same pair of junction points.
For a path of pipes connecting from the barn to the tank, the latency
of the path is the sum of the latencies of the pipes along the path,
and the capacity of the path is the minimum of the capacities of the
pipes along the path (since this is the "bottleneck" constraining the
overall rate at which milk can be pumped through the path). If FJ
wants to send a total of X units of milk through a path of pipes with
latency L and capacity C, the time this takes is therefore L + X/C.
Given the structure of FJ's pipe network, please help him select a single
path from the barn to the storage tank that will allow him to pump X units
of milk in a minimum amount of total time.
PROBLEM NAME: mroute
INPUT FORMAT:
* Line 1: Three space-separated integers: N M X (1 <= X <= 1,000,000).
* Lines 2..1+M: Each line describes a pipe using 4 integers: I J L C.
I and J (1 <= I,J <= N) are the junction points at both ends
of the pipe. L and C (1 <= L,C <= 1,000,000) give the latency
and capacity of the pipe.
SAMPLE INPUT (file mroute.in):
3 3 15
1 2 10 3
3 2 10 2
1 3 14 1
INPUT DETAILS:
FJ wants to send 15 units of milk through his pipe network. Pipe #1
connects junction point 1 (the barn) to junction point 2, and has a latency
of 10 and a capacity of 3. Pipes #2 and #3 are similarly defined.
OUTPUT FORMAT:
* Line 1: The minimum amount of time it will take FJ to send milk
along a single path, rounded down to the nearest integer.
SAMPLE OUTPUT (file mroute.out):
27
OUTPUT DETAILS:
The path 1->3 takes 14 + 15/1 = 29 units of time. The path 1->2->3 takes
20 + 15/2 = 27.5 units of time, and is therefore optimal.
Contest has ended. No further submissions allowed.