Hust oj 1630 网线(MST)

   试设计一个网络连接某个区域中的一些地点。给定这些地点所在的位置，网线的长度就是两个地点的线段距离，假定，给定的网线可以直接或间接的连接该地区中的所有点，试为这个地区设计一个网络系统，使得该地区所有地点都可以直接或间接的连接，并且使用网线长度最短。

输入一个数字n（n<1000），给出这n个点的位置（x,y），即坐标（0≤x＜1000，0≤y＜1000）。

1

1 1

2

0 0

1 1

3

0 0

0 1

1 1

0.0000

1.4142

2.0000

Prim直接水过

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;const int maxn = 1005;
const int Inf = 0x3f3f3f;
struct Node
{double x,y;
}Nd[maxn];double getDis(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}double dis[maxn];
double map[maxn][maxn];
double vis[maxn];
int N;void init()
{for(int i=0;i<N;i++){dis[i] = map[i][0];vis[i] = 0;}
} //距离和访问数组初始化double prim()
{init();dis[0] = 0; //起点距离初始化为0vis[0] = 1; //标记起点double ans = 0; //权值和初始化为0for(int i=0;i<N-1;i++){double temp = Inf; // 记录最小边int flag; //纪录最小点for(int j=0;j<N;j++){if(!vis[j] && dis[j] < temp){temp = dis[j];flag = j;}} //找最小边vis[flag] = 1; //标记选出的边ans += dis[flag]; //把边加入生成树中for(int j=0;j<N;j++){if(!vis[j] && dis[j] > map[flag][j])dis[j] = map[flag][j]; //更新最小权值}}return ans;
}int main()
{while(~scanf("%d",&N)){for(int i=0;i<N;i++){scanf("%lf%lf",&Nd[i].x,&Nd[i].y); //邻接矩阵存图}for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(i == j)map[i][j] = 0;elsemap[i][j] = map[j][i] = getDis(Nd[i].x,Nd[i].y,Nd[j].x,Nd[j].y);}}double ans = prim();printf("%.4lf\n",ans);}return 0;
}