1 人解决,2 人已尝试。
1 份提交通过,共有 3 份提交。
9.7 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
Nineright is manager of a shipping company. With only ONE ship at the beginning of his career, he had to carefully consider the trip to maximize his incoming. But unlike other vehicles, shipping costs much more time.
One day, Nineright comes to you for your help. He is so excited, and said:” help me! I have found the best way to do the business. I would consider the route as a circle that my ship could run every minute! What’s more, I find the route with the maximum average profit is the best. Now, I am going to get them together…”
What a nice idea! You’re going to help him, don’t you!
You are going to get the map as a directed graph. And from city i to city j, you would earn some money pij by do the business. It will cost you ti time to finish that. You are going to find the circle route with maximum average profit!
There are no more than 20 cases. Process to the end of file
Each case begin with N (3 <= N <= 100) represents the number of the city.
Following are N line each with N numbers. The j-th number of the i-th rows stands for the profit you will get if you ship from city i to cit j. with the same format the next N*N number give the time to finish that trip. Pij would be a integer that lies between -1000 and 10000 and The profit pij doesn’t have to be same with pji, because cities have different demands. This is also holds for tij and tji maybe because the weather. Tij would also be an integer lies between 1 and 1000. The i-th number in the i-th row would always be 0;
Output the average of the profit each in one line. be accurate within 0.01.
3 0 59 19 56 0 52 88 26 0 0 7 4 1 0 3 7 6 0
14.4
1 人解决,2 人已尝试。
1 份提交通过,共有 3 份提交。
9.7 EMB 奖励。
创建: 15 年前.
修改: 6 年,11 月前.
最后提交: 3 年,8 月前.
来源: N/A