Let’s Ship

  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 p_ij by do the business. It will cost you t_ij 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. p_ij would be a integer that lies between -1000 and 10000 and The profit p_ij doesn’t have to be same with p_ji, because cities have different demands. This is also holds for t_ij and t_ji maybe because the weather. t_ij 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,and the result should accurate within 0.1.

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

14.4

ZSTU

HDU 2009-12 Programming Contest