uva 10034 - Freckles

題目意思：  給定n個點的坐標，要求找到最短的路徑將這些點鏈接起來

思路：  Prime + 最小生成樹
分析：  給定n個點的坐標，要求找到最短路。很明顯的最小生成樹的題目，利用Prime就可以。這裡記得要先求出每一條邊的長度

代碼：
[cpp]
#include<algorithm> 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
using namespace std; 
#define MAXN 110 
#define INF 0xFFFFFFF 
 
int t , n; 
double  G[MAXN][MAXN]; 
double lowcost[MAXN]; 
double ans; 
int vis[MAXN]; 
struct Point{ 
    double x; 
    double y; 
}p[MAXN]; 
 
void init(){ 
     memset(G , 0 , sizeof(G)); 
     for(int i = 0 ; i < n ; i++){ 
        for(int j = 0 ; j < n ; j++){ 
           if(i == j)  
             continue; 
           double tmp_x , tmp_y; 
           tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x); 
           tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y); 
           G[i][j] = sqrt(tmp_x+tmp_y);  
        } 
     } 
} 
 
void Prime(){ 
     int pos; 
     double min; 
     memset(vis , 0 , sizeof(vis)); 
     vis[0] = 1; 
     ans = 0; 
     for(int i = 0 ; i < n ; i++) 
        lowcost[i] = G[0][i]; 
     for(int i = 0 ; i < n ; i++){ 
        min = INF; 
        for(int j = 0 ; j < n ; j++){ 
           if(!vis[j] && lowcost[j] < min){ 
              min = lowcost[j]; 
              pos = j; 
           } 
        } 
        if(min == INF) 
          break; 
        ans += min; 
        vis[pos] = 1; 
        for(int j = 0 ; j < n ; j++){  
           if(!vis[j] && lowcost[j] > G[pos][j]) 
             lowcost[j] = G[pos][j];       
        } 
     } 
     printf("%.2lf\n" , ans); 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    scanf("%d" , &t); 
    while(t--){ 
        scanf("%d" , &n); 
        for(int i = 0 ; i < n ; i++) 
           scanf("%lf%lf" , &p[i].x , &p[i].y); 
        init(); 
        Prime(); 
        if(t)  
           printf("\n"); 
    } 
    return 0; 
}