UVA534

UVA534 URL:http://uva.onlinejudge.org/external/5/534.pdf

--------------------------------------------------------------

大意 :

有隻青蛙想從A點跳到B點，問你A到B的路徑裡，最短的路徑裡權重最大的邊(最小生成樹的瓶頸)

EX:

path(start,2) = 3,path(2,3) =4 ,path(4,end) = 1 ,the distance is 4.

--------------------------------------------------------------

import java.util.*;
 
class undirected_graph
{
 static double map[][] = new double[205][205];
 static boolean visit[] = new boolean[205];
 static double cost[] = new double[205];
 static int parent[] = new int[205];
 static int n = 0;
 
 void create_map(){
  
  Scanner sc = new Scanner(System.in);
  
  int count =1;
  
  while(sc.hasNext())
  {
   double map[][] = new double[205][205];
   boolean visit[] = new boolean[205];
   double cost[] = new double[205];
      int parent[] = new int[205];
   
   n = sc.nextInt();
  
   sc.nextLine();
  
   if(n==0)break;
  
   System.out.println("Scenario #"+count);
  
   int x_l[] = new int[n];
  
   int y_l[] = new int[n];
  
   for(int N=0;N<n;N++)
   {
    x_l[N] = sc.nextInt();
  
    y_l[N] = sc.nextInt();
   }
   
   sc.nextLine();
  
   for(int i =0;i<n;i++)
    for(int j =0;j<n;j++)
    {  
     map[i][j] =  Math.sqrt((x_l[i]-x_l[j]) * (x_l[i]-x_l[j]) + (y_l[i]-y_l[j])*(y_l[i]-y_l[j]));
     
    }

//prim
   int start = 0,find_v = 0,i = 0; 
   
   double min = 0;
   
   for(int m = 0;m<n;m++)
   {
    cost[m] = map[0][m];
    
   }
   for(int d = 0;d<n;d++)
   {
    visit[d] = false;
    
    if(cost[d]==0)
     cost[d] = Double.MAX_VALUE;
    
    if(cost[d]==Double.MAX_VALUE)
     parent[d] = -1;
    
   }
   cost[0] = 0;
   visit[0] = true;
   find_v=1;
   
   while(find_v<n)
   {
    min = Double.MAX_VALUE;
    start = -1;
    
    for(i = 0 ; i < n ; i++)
    {
     if(visit[i]==false && cost[i]<min)
     {
      start = i;
      min = cost[i];
     
     }
    }
    if(start==-1)break;
    
    visit[start] = true;
    find_v++;
    
    for(i = 0 ; i < n ; i++)
    {
     if(visit[i]==false && map[start][i]<cost[i])
     {
      cost[i] = map[start][i];
      parent[i] = start;
     }
    }
   }
   double maxmimum = 0;
   
   int back = 1;
   
   while(parent[back]!=-1){
    
    if(maxmimum < cost[back])
    {
     maxmimum  = cost[back];
    }
    back = parent[back];
   }
   System.out.printf("Frog Distance = %.3f\n\n",maxmimum);
   count++;
  }
 }
}
public class Main {

 public static void main(String args[]){
  
  undirected_graph g = new undirected_graph(); 
  g.create_map(); 
 }
}