当前位置:编程学习 > C/C++ >>

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; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,