The perfect hamilton path
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 181
Solved: 34
- Description
- There are N(2 <= N <= 13) cities and M bidirectional roads among the cities. There exist at most one road between any pair of the cities. Along every road, there are G pretty girls and B pretty boys(1 <= G,B <= 1000).
You want to visit every city exactly once, and you can start from any city you want to. The degree of satisfaction is the ratio of the number of the pretty girls to the number of the pretty boys. You want to know the highest degree of satisfation.
- Input
- There are multiply test cases.
First line: two integers N, M;
The following M lines: every line with four integers i, j, G, B, response that there is a road between i and j with G and B.
- Output
- The highest degree of the satisfation, rounded to the third place after the decimal point.
- sample input
-
3 3 1 2 5 3 2 3 7 4 3 1 13 11
- sample output
-
1.714
- hint
- source
- dupeng