首页 > 专题系列 > Java解POJ > POJ 2101 Honey and Milk Land [解题报告] Java
2013
11-10

POJ 2101 Honey and Milk Land [解题报告] Java

Honey and Milk Land

问题描述 :

Bad rumors are spreading over the Land of Honey and Milk. Informed people say that the milk in the famous grid of milk rivers is turning sour. Of course, the security service quickly found out that the people are informed by the Kingdom of Tar, which is jealous to tourist popularity of the land. However, this discovery does not help to stop these rumors. The government wants to prevent crisis of the tourist industry, so it wants to establish daily monitoring of the rivers.

A new Milk Security Department is established, which is responsible for preventing the milk from turning sour. It’s equipped with powerful boilers and pasteurizer, so any danger for the milk can be quickly neutralized. To better fight the new threat, the department needs to know about possible dangers beforehand. They have a helicopter, capable to check milk freshness. The equipment is perfect. It’s enough just to cross a river in any place in order to detect all its potentially dangerous places.

To start the Milk Security Department operations, the government needs to add funding of the Service to the Land budget. One of the issues is the morning route of the helicopter. The helicopter should check all the rivers in the shortest time. They need to determine the price of this flight to add it to the budget.

The grid consists of two sets of milk rivers. Rivers from the first set run from North to South, rivers from the second set — from East to West. The rivers are straight. The rivers from each set are parallel and the distance between the adjacent rivers is known. There are n rivers, running from North to South and e rivers, running from East to West.

The government needs to determine the minimal morning flight cost. Each kilometer costs 1 honey barrel, the Land national currency. The cost of take-off and landing is not included into this cost. You may freely choose the starting and ending points of the flight.

输入:

The first line of the input file contains n and e (1 <= n, e <= 1 000). The second line contains n - 1 integer numbers that represent distances (in kilometers) between adjacent rivers running from North to South, listed from East to West. The third line contains e - 1 integer numbers that represent distances (also in kilometers) between adjacent rivers running from East to West, listed from North to South. The distance between any two adjacent rivers does not exceed 27 kilometers.

输出:

Output the minimal morning flight cost in honey barrels. Since there is no smaller denomination, you must output the minimal integer number of honey barrels that would be sufficient to support the flight.

样例输入:

10 10
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2

样例输出:

26

解题代码:

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
   Scanner cin = new Scanner(System.in);
   int n = cin.nextInt();
   int e = cin.nextInt();
   double l1 = 0, l2 = 0;
   while(--n > 0) {
    l1 += cin.nextInt();
   }
   while(--e > 0) {
    l2 += cin.nextInt();
   }
   l1 = Math.hypot(l1, l2);
   System.out.println((int)Math.ceil(l1));
}

}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的