Flow Management ---- ---------- You work for a company that manages the flow of gasoline from refineries in the Southwest to depots in the Northeast. The year is 2473, and things have changed. Gone are all the large companies, and all companies are very small. There are thousands of small companies that each operate a single pipeline from one depot to another, with depots all across the country. Each charges its own price per gallon for transport from the beginning of its pipe to the end of its pipe. The good news is that everything is computerized, so your customers put orders into your computer, your computer puts orders into pipeline company computers, and pipeline company computers turn valves on and off to make things happen. Also, there is no minimum charge for using a pipeline, and the charge is linear in the amount of gasoline per hour, because gasoline is actually batched in tanks at depots and sent down a pipeline in batches, so the cost per gallon is held constant by twiddling the size of the batches. You are your company's software department, and as we said, everything is done automatically by computer. So in a sense, you company is just a computer program. Its called FLOWMAN, the flow manager. Its block diagram is: Customer Pipeline ^ Data | | v queries v REQUESTER -------------------> EVALUATOR ^ | | v +-------------------------> DECIDER | v Pipeline Order Your immediate job is to write a new and better EVALUATOR. This is given queries of the form: What is the maximum flow rate of gasoline in gallons per hour that we can achieve from depot QS to depot QD if we spend up to QC dollars per hour? Given such a query and the current pipeline data, your EVALUATOR must return a number that is the answer to the query. As some point the DECIDER will place an order based on your answers to several queries, and then the pipeline operators will change the pipeline data to reflect the new order. Input ----- A sequence of test cases. Each test case begins with a line containing the test case name. The next line contains D P Q where D is the number of depots, P the number of pipe- lines, and Q the number of queries. Depots have ID numbers 1, 2, ..., D. Then next P lines each describe one pipeline and have the form PS PD PC PP where PS is the source depot ID of the pipeline, PD is the destination depot ID, PC is the capacity of the pipeline given as in integer in gallons per hour, and PP is the price in dollars per gallon to the nearest hund- reth of a cent (0.0001 dollars). Pipelines only work in one direction and cannot maintain a flow greater than their capacity. But they can work with any flow value less than their capacity, including NON-INTEGRAL numbers of gallons per hour. The next Q lines each describe one query and have the form QS QD QC where QS is the source depot ID, QD is the destination depot ID, and QC is the maximum expenditure rate in dollars per hour, given as an integer. For each query you must compute a network flow such that the net flow into every depot but QS and QD is zero, as the flow must be sustained indefinitely. The net flow out of QS must equal the net flow into QD, and this must be maximized given the pipeline capacities and the maximum total expenditure constraint QC. 2 <= D <= 1,000 1 <= P <= 1,000 1 <= Q <= 10 1 <= PC <= 500 0.0100 <= PP <= 1.0000 1 <= QC <= 100,000 sum D*P*Q over all test cases <= 1,000,000 Input ends with an end of file. The test case name line is at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then for each query, just one line giving the maximum flow possible, in gallons per hour, accurate to 0.1 gallon. Each query is evaluated independently of the other queries. Sample Input ------ ----- -- SAMPLE 1 -- 4 5 3 1 2 100 0.1000 1 3 50 0.3000 2 4 100 0.2000 2 3 50 0.0300 3 4 50 0.0700 1 4 10 1 4 25 1 4 40 -- SAMPLE 2 -- 4 5 2 1 2 100 0.1000 2 3 100 0.2000 3 4 100 0.1000 2 1 50 0.0100 4 3 50 0.0200 1 4 25 4 1 25 Sample Output ------ ------ -- SAMPLE 1 -- 50.00 100.00 131.91 -- SAMPLE 2 -- 62.50 0.00 [See sample.flow for pipe flows] File: flowman.txt Author: Bob Walton Date: Tue Oct 15 02:59:55 EDT 2019 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.