poj 2560 uva 10034 - Freckles

点击打开链接uva 10034

题目意思：  给定n个点的坐标，要求找到最短的路径将这些点链接起来

思路：  Prime + 最小生成树

分析：  给定n个点的坐标，要求找到最短路。很明显的最小生成树的题目，利用Prime就可以。这里记得要先求出每一条边的长度

代码：

#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;
}