首页 > ACM题库 > HDU-杭电 > hdu 3196 Let’s Ship待解决[解题报告]C++
2014
03-06

hdu 3196 Let’s Ship待解决[解题报告]C++

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 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!

输入:

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;

输出:

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;

样例输入:

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

样例输出:

14.4


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”