P4951 [USACO01OPEN] Earthquake

An earthquake destroyed John’s farm. Tough John decides to rebuild his home. John has rebuilt $n$ pastures, and now he wants to build some roads to connect them. After studying the terrain, John found that there are $m$ possible roads that can be built. Coincidentally, the cows have recently formed an engineering team specialized in repairing roads. However, the cows are very business-minded: if there is no profit, they will not do the job. The cows care about the speed of making money, that is, the ratio of total profit to total construction time. John and the cows reach an agreement: the cows will build roads to make all pastures connected, and John will pay $f$ dollars. Each road has its own construction time and building cost. There may be multiple roads connecting the same pair of pastures. It is guaranteed that all pastures can be connected, but it is also possible that the sum of building costs of some set of roads exceeds $f$. Please help the cows choose which roads to repair so that the profit per unit time is maximized.

The first line contains three integers $n,m,f$. Lines $2$ to $m+1$ describe the roads. The $(i+1)$-th line gives the information of the $i$-th road: four integers $u_i,v_i,c_i,t_i$, where $u_i$ and $v_i$ are the indices of the pastures this road connects, $c_i$ is the cost to build the road, and $t_i$ is the time required to build the road.

The first line contains a floating-point number rounded to four decimal places, representing the maximum profit per unit time the cows can earn. If the cows cannot make any profit, output `0.0000`.

#### Explanation of Sample Input/Output 1 The cows can choose the last four roads to connect all pastures. Then the total time is $16$ and the total cost is $83$, so the profit per unit time is $\dfrac{17}{16}=1.0625$. #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $1 \leq n \leq 400$, $1 \leq m \leq 10000$, $1 \leq f \leq 2 \times 10^9$. - $1 \leq u_i,v_i \leq n$, $1 \leq c_i,t_i \leq 2 \times 10^9$. Translated by ChatGPT 5