首页 > 专题系列 > Java解POJ > POJ 2485 Highways [解题报告] Java
2013
11-11

POJ 2485 Highways [解题报告] Java

Highways

问题描述 :

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.

输入:

The first line of input is an integer T, which tells how many test cases followed.

The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

输出:

For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

样例输入:

1

3
0 990 692
990 0 179
692 179 0

样例输出:

692

温馨提示:

Huge input,scanf is recommended.

解题代码:

//* @author: 
代码一:
import java.util.Scanner;
public class Main{
        public static void main(String argvs[]){
                int matrix[][];
                int Max=65536;
                int m,n,t,i,j,k,max_len,count,num,min,point=0;
                int temp1[],temp2[],flag[];
                Scanner in=new Scanner(System.in);
                t=in.nextInt();
                for(i=0;i< t;i++){
                    n=in.nextInt();
                    matrix=new int[n][n];
                    flag=new int[n];
                    for(j=0;j< n;j++)
                        flag[j]=0;
                    flag[0]=1;
                    count=0;
                    num=0;
                    min=Max;
                    max_len=0;
                    temp1=new int[n*(n-1)/2];
                    temp2=new int[n*(n-1)/2];
                    for(j=0;j< n;j++)
                        for(k=0;k< n;k++)
                            matrix[j][k]=in.nextInt();
                    for(j=1;j< n;j++){
                        temp1[num]=matrix[0][j];
                        temp2[num]=j;
                        num++;
                    }
                    while(count!=n-1){
                       for(j=0;j< num;j++)
                           if(min>temp1[j]&&flag[temp2[j]]==0){
                               min=temp1[j];
                               point=j;
                           }
                       if(min>max_len) max_len=min;
                       flag[temp2[point]]=1;
                       for(j=0;j< n;j++)
                           if(j!=temp2[point]&&flag[j]==0){
                                temp1[num]=matrix[temp2[point]][j];
                                temp2[num]=j;
                                num++;
                           }
                       min=Max;
                       count++;
                    }
                    System.out.println(max_len);
                }
        }
}

代码二:
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int w=Integer.parseInt(in.readLine());
  while((w--)!=0)
  {
   in.readLine();
   int a=Integer.parseInt(in.readLine());
   int[][] p=new int[a][a];
   int[] key=new int[a];
   boolean[] used=new boolean[a];
   for(int i=0;i< a;i++)
   {
     String[] ss=in.readLine().split(" ");
     for(int j=0;j< a;j++)
	p[i][j]=Integer.parseInt(ss[j]);
   }
  for(int i=0;i< a;i++)
   key[i]=p[i][0];
  int ans=0,tag=0,min;
  used[0]=true;
  for(int i=0;i< a-1;i++)
  {
   min=99999999;
   tag=0;
   for(int j=0;j< a;j++)
    if(!used[j]&&key[j]< min)
    {
     min=key[j];
     tag=j;
    }
   if(min>ans) ans=min;
   used[tag]=true;
   for(int j=0;j< a;j++)
   {
    if(!used[j]&&p[j][tag]< key[j])
	key[j]=p[j][tag];
   }
  }
  System.out.println(ans);
  }
 }
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。