Let’s Ship

Time Limit: 3000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3196
64-bit integer IO format: %I64d      Java class name: Main

Description

  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 tij time to finish that. You are going to find the circle route with maximum average profit!

Input

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

Output the average of the profit each in one line,and the result should accurate within 0.1.

Sample Input

3
0 59 19
56 0 52
88 26 0
0 7 4
1 0 3
7 6 0

Sample Output

14.4

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .