刚开始题目看错了,一直wa,输入的坐标是浮点型。。。。。。。
听了队友的,才知道prim算法只需要枚举到sqrt(n)就完全足够了,发现sqrt(n)好多地方用的到。
1 #include<stdio.h>
2 #include<math.h>
3
4 const int MAXN=510;
5 const int INF=0x7fffffff;
6 struct Node
7 {
8 double x,y;
9 } node[MAXN];
10
11 double temp;
12 double dist[MAXN];//dist[i]表示i向外延伸的最短边长
13 double map[MAXN][MAXN];//储存a->b之间的边权值
14 int pre[MAXN];//pre[i]记录i的父节点
15 int n,m;
16
17 double _dist(Node a,Node b)
18 {
19 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
20 }
21
22 void Prim(int s)
23 {
24 int i,j,k;
25 double min;
26 bool p[MAXN];//区分Va集合和Vb集合
27 for(i=1; i<=n; i++)
28 {
29 p[i]=false;
30 dist[i]=map[s][i];
31 pre[i]=s;
32 }
33 dist[s]=0;
34 p[s]=true;
35 for(i=1; i<=n-1; i++) //循环n-1次,每次加入一个点
36 {
37 min=INF;
38 k=0;
39 for(j=1; j<=n; j++)
40 {
41 //若j还在Vb集合中,并且j的路径可以再小点(找当前i点所对应的最短权值)
42 if(!p[j] && dist[j]<min)
43 {
44 min=dist[j];
45 k=j;
46 }
47 }
48 if(k==0) return ;//如果没有点可以扩展,即图G不连通,返回
49 if(temp<dist[k]) temp=dist[k];
50 if(i==m) return ;
51 p[k]=true;//将点k移到Va集合
52 for(j=1; j<=n; j++) //更新相邻k相邻的点(有些dist依旧记录着以前Va结点中相邻的点)
53 {
54 //对于每个与k相邻的Vb中的点j,更新j距离最近的点及其距离
55 if(!p[j] && map[k][j]!=INF && dist[j]>map[k][j])
56 {
57 dist[j]=map[k][j];
58 pre[j]=k;
59 }
60 }
61 }
62 }
63
64 int main()
65 {
66 int T,i,j;
67 scanf("%d",&T);
68 while(T--)
69 {
70 scanf("%d%d",&n,&m);
71 for(i=1; i<=n; i++)
72 {
73 scanf("%lf%lf",&node[i].x,&node[i].y);
74 }
75 for(i=1; i<=n; i++)
76 {
77 for(j=1; j<=n; j++)
78 {
79 map[i][j]=_dist(node[i],node[j]);
80 }
81 }
82 double res=INF;
83 for(i=1; i*i<=n; i++)//////
84 {
85 temp=0;
86 Prim(i);
87 if(res>temp) res=temp;
88 }
89 printf("%.4lf\n",res);
90 }
91 return 0;
92 }