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++ ,