We want to build a new phone network between numPoints points. A number of possible cables is available to construct the network. Each of the cables connects two of the points and has an associated quality and cost. We want to select a number of these cables such that:
1) All the points are connected to each other, either directly or via other points.
2) The quality/cost ratio (i.e., the sum of the qualities divided by the sum of the costs) is as high as possible.
What is the best achievable ratio? If it is impossible to connect all the points, return -1.
The available cables are described by a String cables. Each element of cables consists of four integers separated by single spaces. The first two integers describe the two points connected by the cable. The third integer describes the quality of the cable and the fourth integer describes its cost.
|-||Your return must have relative or absolute error less than 1e-9.|
|-||numPoints is between 2 and 50, inclusive.|
|-||cables has between 0 and 50 elements, inclusive.|
|-||Each element of cables has length between 0 and 50, inclusive.|
|-||Each element of cables consists of four integers with no leading zeroes, separated by single spaces.|
|-||The first two integers of each element of cables are between 1 and numPoints, inclusive.|
|-||The first two integers of each element of cables are not equal.|
|-||The third and fourth integers of each element of cables are between 1 and 100,000, inclusive.|